Skip to content

Instantly share code, notes, and snippets.

@kusano

kusano/FoxConnection3.cpp

Created February 28, 2015 18:36
Show Gist options
  • Save kusano/c77cef061c61ad492aa4 to your computer and use it in GitHub Desktop.
Save kusano/c77cef061c61ad492aa4 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
FoxConnection3.cpp
#include <vector>
#include <algorithm>
using namespace std;
// BEGIN CUT HERE
#include <iostream>
#include <sstream>
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v);
// END CUT HERE
int P[7][64][6][2] =
{
// 0
{
},
// 1
{
{{0,0}},
},
// 2
{
{{0,0}, {0,1}},
},
// 3
{
{{0,0}, {0,1}, {0,2}},
{{0,0}, {0,1}, {1,0}},
},
// 4
{
{{0,0}, {0,1}, {0,2}, {0,3}},
{{0,0}, {0,1}, {1,0}, {1,1}},
{{0,0}, {0,1}, {0,2}, {1,0}},
{{0,0}, {0,1}, {1,1}, {1,2}},
{{0,0}, {0,1}, {0,2}, {1,1}},
},
// 5
{
{{0,0}, {0,1}, {0,2}, {0,3}, {0,4}},
{{0,0}, {0,1}, {0,2}, {1,0}, {1,1}},
{{0,0}, {0,1}, {0,2}, {0,3}, {1,0}},
{{0,1}, {0,2}, {1,0}, {1,1}, {2,1}},
{{0,0}, {0,1}, {0,2}, {1,2}, {1,3}},
{{0,0}, {0,1}, {0,2}, {1,1}, {2,1}},
{{0,0}, {0,1}, {0,2}, {1,0}, {1,2}},
{{0,0}, {0,1}, {0,2}, {1,0}, {2,0}},
{{0,1}, {0,2}, {1,0}, {1,2}, {2,0}},
{{0,1}, {1,0}, {1,1}, {1,2}, {2,1}},
{{0,0}, {0,1}, {0,2}, {0,3}, {1,1}},
{{0,0}, {1,0}, {1,1}, {1,2}, {2,2}},
},
// 6
{
{{0,0}, {0,1}, {0,2}, {0,3}, {0,4}, {0,5}},
{{0,0}, {0,1}, {0,2}, {0,3}, {0,4}, {1,0}},
{{0,0}, {0,1}, {0,2}, {0,3}, {0,4}, {1,1}},
{{0,0}, {0,1}, {0,2}, {0,3}, {0,4}, {1,2}},
{{0,0}, {0,1}, {0,2}, {0,3}, {1,3}, {1,4}},
{{0,0}, {0,1}, {0,2}, {0,3}, {1,0}, {1,1}},
{{0,0}, {0,1}, {0,2}, {0,3}, {1,0}, {1,2}},
{{0,0}, {0,1}, {0,2}, {0,3}, {1,0}, {1,3}},
{{0,0}, {0,1}, {0,2}, {0,3}, {1,1}, {1,2}},
{{0,0}, {0,1}, {0,2}, {0,3}, {1,0}, {2,0}},
{{0,0}, {0,1}, {0,2}, {0,3}, {1,1}, {2,1}},
{{0,0}, {0,1}, {0,2}, {1,1}, {2,1}, {3,1}},
{{1,0}, {1,1}, {1,2}, {1,3}, {0,0}, {2,1}},
{{1,0}, {1,1}, {1,2}, {1,3}, {0,0}, {2,2}},
{{1,0}, {1,1}, {1,2}, {1,3}, {0,0}, {2,3}},
{{1,0}, {1,1}, {1,2}, {1,3}, {0,1}, {2,2}},
{{1,0}, {1,1}, {1,2}, {1,3}, {0,1}, {2,1}},
{{1,0}, {1,1}, {1,2}, {0,1}, {2,0}, {3,0}},
{{0,0}, {0,1}, {0,2}, {1,0}, {1,2}, {1,3}},
{{0,0}, {0,1}, {0,2}, {1,2}, {1,3}, {1,4}},
{{0,0}, {0,1}, {0,2}, {1,1}, {1,2}, {1,3}},
{{0,0}, {0,1}, {0,2}, {1,0}, {1,1}, {1,2}},
{{1,0}, {1,1}, {1,2}, {0,0}, {2,1}, {3,1}},
{{0,0}, {0,1}, {0,2}, {1,0}, {1,1}, {2,1}},
{{0,0}, {0,1}, {1,1}, {1,2}, {1,3}, {2,2}},
{{0,0}, {0,1}, {0,2}, {1,2}, {2,2}, {2,3}},
{{0,0}, {0,1}, {0,2}, {1,2}, {1,3}, {2,3}},
{{0,0}, {0,1}, {0,2}, {1,2}, {2,1}, {2,2}},
{{0,0}, {0,1}, {0,2}, {1,1}, {2,1}, {2,2}},
{{0,0}, {0,1}, {1,1}, {1,2}, {2,0}, {2,1}},
{{0,0}, {0,1}, {1,1}, {1,2}, {1,3}, {2,3}},
{{0,0}, {0,1}, {0,2}, {1,0}, {1,1}, {2,0}},
{{0,0}, {0,1}, {1,0}, {1,1}, {1,2}, {2,1}},
{{0,0}, {0,1}, {1,0}, {1,1}, {2,1}, {2,2}},
{{0,0}, {0,1}, {1,1}, {1,2}, {2,2}, {2,3}},
},
};
int Pn[7] = {0, 1, 1, 2, 5, 12, 35};
class FoxConnection3{public:
long long minimalSteps( vector <int> x, vector <int> y )
{
int n = (int)x.size();
long long inf = 0x7fffffffffffffffLL;
long long ans = inf;
for (int p=0; p<Pn[n]; p++)
for (int d=0; d<8; d++)
{
vector<int> T;
for (int i=0; i<n; i++)
T.push_back(i);
do
{
int tx[6];
int ty[6];
for (int i=0; i<n;i++)
{
tx[i] = P[n][p][T[i]][d&1?0:1] * (d&2?-1:1);
ty[i] = P[n][p][T[i]][d&1?1:0] * (d&4?-1:1);
}
long long dx = inf;
for (int i=0; i<n; i++)
{
long long s = tx[i] - x[i];
long long t = 0;
for (int j=0; j<n; j++)
t += abs(tx[j] - (x[j]+s));
dx = min(dx, t);
}
long long dy = inf;
for (int i=0; i<n; i++)
{
long long s = ty[i] - y[i];
long long t = 0;
for (int j=0; j<n; j++)
t += abs(ty[j] - (y[j]+s));
dy = min(dy, t);
}
ans = min(ans, dx+dy);
}
while (next_permutation(T.begin(), T.end()));
}
return ans;
}};
// BEGIN CUT HERE
#include <ctime>
double start_time; string timer()
{ ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
{ os << "{ ";
for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
void verify_case(const long long& Expected, const long long& Received) {
bool ok = (Expected == Received);
if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl;
cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
#define END verify_case(_, FoxConnection3().minimalSteps(x, y));}
int main(){
CASE(0)
int x_[] = {0,0,1,-2};
vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
int y_[] = {1,-1,0,0};
vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_));
long long _ = 2LL;
END
CASE(1)
int x_[] = {0,0,0,0,0,0};
vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
int y_[] = {1,2,3,4,5,6};
vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_));
long long _ = 0LL;
END
CASE(2)
int x_[] = {-123456789,-58585858,-47474747,123,456,789012345};
vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
int y_[] = {0,0,0,0,0,0};
vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_));
long long _ = 1018530309LL;
END
CASE(3)
int x_[] = {1,7,3,5,2};
vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
int y_[] = {2,7,5,3,7};
vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_));
long long _ = 12LL;
END
CASE(4)
int x_[] = {-3,0,1,-2,3,2};
vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
int y_[] = {2,-3,0,1,-1,-1};
vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_));
long long _ = 10LL;
END
CASE(5)
int x_[] = {-96277832,507856257,-86306299,-806700273,-775932643,-273209838};
vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
int y_[] = {-955536464,-599634138,399850429,-165706338,-537800480,738983556};
vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_));
long long _ = 5247213600LL;
END
CASE(6)
int x_[] = {0};
vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
int y_[] = {0};
vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_));
long long _ = 0LL;
END
}
// END CUT HERE
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment