-
-
Save naoyat/e6336534425bf787731722a66af2d8b8 to your computer and use it in GitHub Desktop.
MM93:最終submitコード
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <sstream> | |
#include <fstream> | |
#include <vector> | |
#include <map> | |
#include <set> | |
#include <queue> | |
#include <string> | |
#include <utility> | |
#include <algorithm> | |
#include <cstdio> | |
#include <cstdlib> | |
#include <cstring> | |
#include <cmath> | |
#include <time.h> | |
using namespace std; | |
#define rep(i,n) for(int i=0;i<n;++i) | |
#define tr(i,c) for(auto i=(c).begin(); i!=(c).end(); i++) | |
#define rtr(i,c) for(auto i=(c).rbegin(); i!=(c).rend(); i++) | |
#define found(s,e) ((s).find(e)!=(s).end()) | |
#define all(a) (a).begin(),(a).end() | |
#define rall(a) (a).rbegin(),(a).rend() | |
typedef pair<int, int> ii; | |
typedef pair<double, double> dd; | |
typedef long long ll; | |
#define iirev(x) ii((x).second,(x).first) | |
double _time_limit = 8.5; | |
//typedef double Distance; | |
typedef float Distance; | |
//#define DEBUG 1 | |
//#define VERBOSE 1 | |
///#define TIME_MEASUREMENT 1 | |
//#define PRECISE_ISLE_DISTANCE 1 ///no | |
#define ADD_NOISE 1 | |
#define DO_SHUFFLE 1 | |
#if 1 | |
#ifdef DEBUG | |
#undef NDEBUG | |
#include "cout11.h" | |
#endif | |
#endif | |
#include <cassert> | |
inline int square(int x) { return x*x; } | |
inline int square_distance(int dx, int dy) { return dx*dx + dy*dy; } | |
#define RC(r,c) ((r)*S+(c)) | |
#define IJ(i,j) ((i)*32768+(j)) | |
#define I_of_IJ(ij) ((ij)/32768) | |
#define J_of_IJ(ij) ((ij)%32768) | |
int _clock_called = 0; | |
inline double time() { | |
clock_t t = clock(); | |
++_clock_called; | |
return (double)t / CLOCKS_PER_SEC; | |
} | |
#ifdef TIME_MEASUREMENT | |
#define TIME_FROM(x) double x=time() | |
#define TIME_TO(x,msg) if (_verbose) fprintf(stderr," [time]%s: %g msec\n",string(msg).c_str(),(time()-x)*1000) | |
#else | |
#define TIME_FROM(x) | |
#define TIME_TO(x,msg) | |
#endif | |
ll _mem = 0LL; | |
#ifdef VERBOSE | |
bool _verbose = true; | |
#else | |
bool _verbose = false; | |
#endif | |
#ifdef EXPORT | |
bool _export = true; | |
#else | |
bool _export = false; | |
#endif | |
#ifdef DO_CHECK | |
bool _check = true; | |
#else | |
bool _check = false; | |
#endif | |
int _otc = 0; | |
bool _otflag = false; | |
double _otdelay = 0; | |
bool overtime_check(double qtx) { | |
++_otc; | |
_otdelay = time() - qtx; | |
if (_otdelay >= 0) { | |
if (_verbose) { | |
// fprintf(stderr, "\t// %g ; overtime = %gmsec\n", now, _otdelay*1000); | |
} | |
_otflag = true; | |
} else { | |
_otflag = false; | |
} | |
return _otflag; | |
} | |
class UnionFind { | |
vector<int> data; | |
public: | |
UnionFind(int size) : data(size, -1) { } | |
bool unionSet(int x, int y) { | |
x = root(x); y = root(y); | |
if (x != y) { | |
if (data[y] < data[x]) swap(x, y); | |
data[x] += data[y]; data[y] = x; | |
} | |
return x != y; | |
} | |
bool findSet(int x, int y) { return root(x) == root(y); } | |
int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); } | |
int size(int x) { return -data[root(x)]; } | |
}; | |
typedef pair<int, int> Isle; | |
int _dr[4] = {0,0,1,1}, _dc[4] = {0,1,1,0}; | |
inline void isle_put(vector<ii>& out, int& lastr, int& lastc, Isle here, Isle next_isle) { | |
// fprintf(stderr, "put(%d,%d - %d,%d - %d,%d)...\n", lastr,lastc, r,c, nextr,nextc); | |
int r = here.first, c = here.second; | |
int nxr = next_isle.first, nxc = next_isle.second; | |
#if 1 | |
//bool log=(lastr==3 && lastc==15); | |
Distance min_d = 1000.0; | |
ii min_at(-1, -1); | |
rep(i, 4) { | |
int ur = r+_dr[i], uc = c+_dc[i]; | |
Distance du = hypot(ur - lastr, uc - lastc); | |
//if(log) fprintf(stderr, "[]i=%d, u(%d,%d),du=%g\n", i,ur,uc,du); | |
if (du == 0) continue; | |
for (int j=1; j<=3; j+=2) { | |
int vr = r+_dr[(i+j)%4], vc = c+_dc[(i+j)%4]; | |
int dr = (vr <= nxr) ? nxr-vr : vr-(nxr+1); | |
int dc = (vc <= nxc) ? nxc-vc : vc-(nxc+1); | |
Distance dv = hypot(dr, dc); | |
Distance d = du + dv; | |
//if(log) fprintf(stderr, " []j=%d, v(%d,%d),dv=%g,d=%g\n", j,vr,vc,dv,d); | |
if (d < min_d) { | |
min_d = d; | |
min_at = ii(i, j); | |
} | |
} | |
} | |
int i = min_at.first, j = min_at.second; | |
// fprintf(stderr, "isle_put (%d,%d) - (%d,%d) - (%d,%d): i=%d j=%d\n", | |
// lastr,lastc, r,c, nxr,nxc, i,j); | |
int ix[4] = {i, (i+2)%4, (i+j+2)%4, (i+j)%4}; | |
set<int> _s; | |
rep(k, 4) { | |
out.push_back(ii(r+_dr[ix[k]], c+_dc[ix[k]])); | |
_s.insert(ix[k]); | |
} | |
assert(_s.size() == 4); | |
lastr = r+_dr[ix[3]]; | |
lastc = c+_dc[ix[3]]; | |
#else | |
int dmin = 1000000, d_at = -1; | |
rep(i, 4) { | |
int d_ = square_distance(r+(i&1) - lastr, c+(i>>1) - lastc); | |
if (0 < d_ && d_ < dmin) { dmin = d_; d_at = i; } | |
} | |
// fprintf(stderr, " d_at=%d, dmin=%d\n", d_at, dmin); | |
assert(d_at != -1); | |
out.push_back(ii(r+(d_at&1), c+(d_at>>1))); | |
out.push_back(ii(r+1-(d_at&1), c+1-(d_at>>1))); | |
int fmin = 1000000, f_at = -1; | |
rep(i, 4) { | |
int f_ = square_distance(r+(i&1) - nxr, c+(i>>1) - nxc); | |
// if (0 < d_ && d_ < dmin) { fmin = d_; f_at = i; } | |
// if (d_ == 0) continue; | |
if (f_ < fmin) { fmin = f_; f_at = i; } | |
} | |
// fprintf(stderr, " f_at=%d, fmin=%d\n", f_at, fmin); | |
assert(f_at != -1); | |
if (f_at == d_at || f_at == 3 - d_at) { // 0-3 1-2 2-1 3-0 | |
// int alternative[4] = { 1, 0, 3, 2 }; | |
// f_at = alternative[d_at]; | |
f_at = d_at ^ 1; | |
assert(f_at != 3 - d_at); | |
} | |
out.push_back(ii(r+1-(f_at&1), c+1-(f_at>>1))); | |
out.push_back(ii(r+(f_at&1), c+(f_at>>1))); | |
lastr = r+(f_at&1); | |
lastc = c+(f_at>>1); | |
#endif | |
} | |
void isle_render(vector<ii>& out, Isle here, int& lastr, int& lastc, Isle prev_isle=Isle(-1,-1), Isle next_isle=Isle(-1,-1)) { | |
//int lastr = last.first, lastc = last.second; | |
if (lastr == -1 && prev_isle.first >= 0) { | |
lastr = prev_isle.first; | |
lastc = prev_isle.second; | |
} | |
if (next_isle.first == -1) next_isle = here; //Isle(100, 100); | |
isle_put(out, lastr, lastc, here, next_isle); // updates lastr and lastc | |
} | |
#define TASK_NAIVE 1 | |
#define TASK_WINDOW 2 | |
#define TASK_LINE 3 | |
#define TASK_UF 4 | |
#define TASK_TSP4 5 | |
class Task { | |
public: | |
int S; | |
int color; | |
int task_type; | |
string caption; | |
int mode; | |
bool do_tsp_greedy; | |
bool improved_greedy; | |
double shuffle; | |
vector<Isle> isles; | |
// double time_limit; | |
vector<int> path; | |
vector<vector<Distance> > distance_table; | |
vector<Distance> md; // mean distance from a verted | |
bool initialized; | |
bool converged; | |
int size() { return this->isles.size(); } | |
// TSP4 | |
vector<ii> path4; | |
vector<vector<Distance> > distance_table4; | |
vector<Distance> md4; // mean distance from a verted | |
public: | |
Task(int S, int color, int task_type, char *caption, int mode, bool do_tsp_greedy, bool improved_greedy, double shuffle) { | |
this->S = S; | |
this->color = color; //pp | |
this->task_type = task_type; | |
// this->time_limit = 0; | |
this->caption = string(caption); | |
this->mode = mode; | |
this->do_tsp_greedy = do_tsp_greedy; | |
this->improved_greedy = improved_greedy; | |
this->shuffle = shuffle; | |
this->isles.clear(); | |
initialized = false; | |
converged = false; | |
} | |
~Task() { | |
// int M = size(); | |
int W = distance_table.size(); | |
vector<vector<Distance> >().swap(distance_table); | |
vector<Distance>().swap(md); | |
vector<int>().swap(path); | |
_mem -= sizeof(Distance) * (W*W + W); | |
_mem -= sizeof(int)*W; | |
int W4 = distance_table4.size(); | |
vector<vector<Distance> >().swap(distance_table4); | |
vector<Distance>().swap(md4); | |
vector<ii>().swap(path4); | |
_mem -= sizeof(Distance) * (W4*W4 + W); | |
_mem -= sizeof(ii)*W; | |
vector<Isle>().swap(isles); | |
} | |
public: | |
string desc() { | |
stringstream ss; | |
ss << caption << ", " | |
// << "color=" << (char)color << ", " | |
<< "S=" << S << ", " | |
<< "|isles|=" << isles.size() << ", "; | |
if (path4.size() > 0) { | |
ss << "|path4|=" << path4.size() << ", "; | |
} else { | |
ss << "|path|=" << path.size() << ", "; | |
} | |
ss << "W=" << size(); | |
// fprintf(stderr, "TSP(S=%d, color=%c, |isles|=%d)\n", task->S, task->color, M); | |
return ss.str(); | |
} | |
}; | |
#ifdef DEBUG | |
void export_solution(const char *filename, int S, vector<Isle>& isles, vector<ii>& out) { | |
ofstream f; | |
f.open(filename); if (!f) return; | |
f << S << endl; | |
int M = isles.size(); | |
f << M << endl; | |
rep(i, M) { | |
f << 1 << endl; // R | |
f << 1 << " " << isles[i].first << " " << isles[i].second << endl; | |
} | |
int L = out.size(); | |
f << L << endl; | |
rep(i, L) f << out[i].first << " " << out[i].second << endl; | |
f.close(); | |
} | |
#endif | |
//inline Distance dd_distance(dd p1, dd p2) { | |
// return hypot(p1.first - p2.first, p1.second - p2.second); | |
//} | |
inline Distance isle_hypot(Isle isle1, Isle isle2) { | |
int r1 = isle1.first, c1 = isle1.second; | |
int r2 = isle2.first, c2 = isle2.second; | |
return hypot(r2 - r1, c2 - c1); | |
} | |
inline Distance isle_distance(Isle isle1, Isle isle2) { | |
int r1 = isle1.first, c1 = isle1.second; | |
int r2 = isle2.first, c2 = isle2.second; | |
#ifdef PRECISE_ISLE_DISTANCE | |
int dr = max(0, abs(r2 - r1) - 1); | |
int dc = max(0, abs(c2 - c1) - 1); | |
return hypot(dr, dc); | |
#else | |
// if (r1 == r2 && c1 == c2) return 0; | |
Distance sum = 0; | |
rep(i,4) rep(j,4) { | |
Distance d = hypot((r1+_dr[i]) - (r2+_dr[j]), (c1+_dc[i]) - (c2+_dc[j])); | |
if (d < 1.0) d = 1.0; | |
// if (d < 0.5) d = 0.5; | |
sum += d; | |
} | |
sum /= 16; | |
return sum; | |
// return max((Distance)1.0, sum); | |
#if 0 | |
Distance d = hypot(r1 - r2, c1 - c2); | |
if (abs(d - sum) > 1e-9) { | |
cerr << "isle_distance(" << isle1.first << " " << isle1.second << ", " << isle2.first << " " << isle2.second << ") differs." << endl; | |
} | |
return sum; | |
#endif | |
#endif | |
} | |
// #define USE_CENTER_POINT 1 | |
// #define USE_BOTH_ENDS 2 | |
// inline int int_distance(Distance d) { return (int)(d * 100); } | |
#ifdef ADD_NOISE | |
inline double rnd() { | |
#if 1 | |
#define NOISE_N 6 | |
#define NOISE_K 0.15 | |
double rsum = 0.0; | |
rep(i, NOISE_N) { | |
double r = 0.001 * (rand() % 1000 - 500); | |
// double r = 0.001 * (rand() % 500); | |
rsum += r; | |
} | |
rsum /= NOISE_N; | |
return rsum * NOISE_K; | |
#else | |
double r = 0.001 * (rand() % 1000 - 500); | |
r = r*r * 0.01; | |
return r; | |
#endif | |
} | |
#endif | |
void shuffle(vector<int>& v) { | |
int L = v.size(); | |
for (int i=L; i>1; --i) { | |
int a = i-1; | |
int b = rand() % i; | |
swap(v[a], v[b]); | |
} | |
} | |
void partial_shuffle(vector<int>& v, double rate) { | |
int L = v.size(); | |
for (int i=L; i>1; --i) { | |
int a = i-1; | |
if (rand() % 10000 < rate*10000) { | |
int b = rand() % i; | |
swap(v[a], v[b]); | |
} | |
} | |
} | |
void make_distance_table(Task *task) { | |
//TIME_FROM(t1); | |
int M = task->isles.size(); | |
int distance_table_size = M+1; | |
_mem += sizeof(Distance) * distance_table_size * distance_table_size; | |
task->distance_table.assign(M+1, vector<Distance>(distance_table_size, 1000.0)); | |
rep(i, distance_table_size) { | |
task->distance_table[i][i] = 0; | |
} | |
for (int i=0; i<M-1; ++i) { | |
for (int j=i+1; j<M; ++j) { | |
Distance d = isle_distance(task->isles[i], task->isles[j]); | |
task->distance_table[i][j] = task->distance_table[j][i] = d; // int_distance(d); | |
} | |
} | |
rep(i, M) { | |
task->distance_table[i][M] = task->distance_table[M][i] = -5; | |
} | |
if (task->improved_greedy) { | |
task->md.resize(distance_table_size); | |
rep(i, distance_table_size) { | |
Distance sum = 0; | |
rep(j, distance_table_size) sum += task->distance_table[i][j]; | |
// we don't have to skip i==j because distance[i][j] == 0 | |
// task->md[i] = (sum + distance_table_size/2) / distance_table_size; | |
task->md[i] = sum / distance_table_size; | |
} | |
} | |
//TIME_TO(t1,"<"+to_string(task->mode)+">make_distance_table"); | |
} | |
void tsp_greedy(Task *task) { | |
assert(task->mode != 0); | |
//TIME_FROM(t0); | |
// int mode = task->mode; | |
int W = task->distance_table.size(); | |
task->path.clear(); | |
//TIME_FROM(t2); | |
priority_queue<pair<int, int> > pq; // edges | |
for (int i=0; i<W-1; ++i) { | |
for (int j=i+1; j<W; ++j) { | |
Distance d = task->distance_table[i][j]; | |
if (task->improved_greedy) { | |
d -= task->md[i] + task->md[j]; | |
} | |
#ifdef ADD_NOISE | |
d += rnd(); | |
#endif | |
pq.push(make_pair(-d, IJ(i,j))); | |
} | |
} | |
_mem += (sizeof(Distance) + sizeof(int)) * W*(W-1)/2; | |
vector<vector<int> > edge_to(W); | |
UnionFind uf(W); | |
_mem += sizeof(int) * W * 3; | |
// greedy | |
int path_length = 0; | |
for (int i=0; i<W; ) { | |
if (pq.empty()) break; | |
Distance d = -pq.top().first; int edge = pq.top().second; pq.pop(); | |
int p1 = I_of_IJ(edge), p2 = J_of_IJ(edge); | |
if (edge_to[p1].size() < 2 && edge_to[p2].size() < 2 | |
&& (uf.root(p1) != uf.root(p2) || i == W-1)) { | |
uf.unionSet(p1, p2); | |
edge_to[p1].push_back(p2); | |
edge_to[p2].push_back(p1); | |
path_length += d; | |
++i; | |
} | |
} | |
while (!pq.empty()) pq.pop(); | |
_mem -= (sizeof(Distance) + sizeof(int)) * W*(W-1)/2; | |
rep(i, W) { | |
if (edge_to[i].size() != 2) { | |
#ifdef DEBUG | |
if (_verbose) { | |
fprintf(stderr, "M=%d,", W); | |
// cerr << edge_to << endl; | |
} | |
#endif | |
break; | |
} | |
// assert(edge_to[i].size() == 2); | |
} | |
//TIME_TO(t2,"<"+to_string(task->mode)+">greedy"); | |
// find the route | |
//TIME_FROM(t3); | |
set<int> passed; | |
for (int i=0,curr=0; i<W; ++i) { | |
passed.insert(curr); | |
task->path.push_back(curr); | |
int next = -1; | |
rep(j, 2) { | |
int x = edge_to[curr][j]; | |
if (!found(passed, x)) { | |
next = x; break; | |
break; | |
} | |
} | |
if (next == -1) break; | |
curr = next; | |
} | |
//edge_to.clear(); | |
vector<vector<int> >().swap(edge_to); | |
_mem -= sizeof(int) * W * 3; | |
assert(task->path.size() == W); | |
_mem += sizeof(int) * W; | |
//TIME_TO(t3,"<"+to_string(task->mode)+">find the route"); | |
//TIME_TO(t0,"<"+to_string(task->mode)+">tsp_greedy"); | |
} | |
#define MU(m,u) ((m)*4+(u)) | |
#define M_of_MU(mu) ((mu)/4) | |
#define U_of_MU(mu) ((mu)%4) | |
#define SAME_POINT 2001 | |
void make_distance_table4(Task *task) { | |
assert(task->task_type == TASK_TSP4); | |
int M = task->isles.size(); | |
task->path.clear(); | |
int distance_table_size = M+1; | |
task->distance_table4.assign(distance_table_size*4, vector<Distance>(distance_table_size*4, 1000)); | |
_mem += sizeof(Distance) * distance_table_size * distance_table_size * 16; | |
// inner self | |
rep(i, M) { | |
rep(u,4) { // 0 1 2 3 | |
int plus = MU(i, (u+1)%4), minus = MU(i, (u+3)%4); | |
task->distance_table4[plus][minus] = task->distance_table4[minus][plus] = 0; | |
} | |
} | |
// with M | |
rep(u,4) rep(v, 4) { | |
task->distance_table4[MU(M,u)][MU(M,v)] = task->distance_table4[MU(M,v)][MU(M,u)] = 0; | |
} | |
rep(i, M) { | |
rep(u,4) rep(v,4) { | |
task->distance_table4[MU(i,u)][MU(M,v)] = task->distance_table4[MU(M,v)][MU(i,u)] = -1; | |
} | |
} | |
for (int i=0; i<M-1; ++i) { | |
for (int j=i+1; j<M; ++j) { | |
int ri = task->isles[i].first, ci = task->isles[i].second; | |
int rj = task->isles[j].first, cj = task->isles[j].second; | |
rep(u,4) rep(v,4) { | |
Distance d = hypot((ri+_dr[u]) - (rj+_dr[v]), | |
(ci+_dc[u]) - (cj+_dc[v])); | |
if (d == 0) d = SAME_POINT; | |
int iu = MU(i,u), jv = MU(j,v); | |
task->distance_table4[iu][jv] = task->distance_table4[jv][iu] = d; | |
/// pq.push(make_pair(-d, ii(iu,jv))); | |
} | |
} | |
} | |
if (task->improved_greedy) { | |
task->md4.resize(distance_table_size); | |
rep(i, distance_table_size) { | |
Distance sum = 0; | |
rep(u, 4) { | |
int iu = MU(i,u); | |
rep(j, distance_table_size) { | |
rep(v, 4) { | |
int jv = MU(j,v); | |
sum += task->distance_table4[iu][jv]; | |
} | |
} | |
} | |
sum /= 16; | |
// we don't have to skip i==j because distance[i][j] == 0 | |
task->md4[i] = sum / distance_table_size; | |
} | |
} | |
_mem += sizeof(Distance) * distance_table_size; | |
} | |
void tsp4_greedy(Task *task) { | |
assert(task->task_type == TASK_TSP4); | |
// assert(task->mode == 2); | |
int M = task->isles.size(), W = M+1; | |
// greedy | |
priority_queue<pair<Distance, ii> > pq; // edges | |
for (int i=0; i<W-1; ++i) { | |
for (int j=i+1; j<W; ++j) { | |
int ri = task->isles[i].first, ci = task->isles[i].second; | |
int rj = task->isles[j].first, cj = task->isles[j].second; | |
rep(u,4) rep(v,4) { | |
int iu = MU(i,u), jv = MU(j,v); | |
Distance d = task->distance_table4[iu][jv]; | |
if (task->improved_greedy) { | |
d -= task->md4[i] + task->md4[j]; | |
} | |
#if 0 | |
d += 0.002 * (rand() % 1000); | |
#endif | |
pq.push(make_pair(-d, ii(iu,jv))); | |
} | |
} | |
} | |
_mem += (sizeof(Distance) + sizeof(int)*2) * W*(W-1)/2 * 16; | |
vector<vector<ii> > edge_to(W); | |
vector<int> used_h(W, 0); | |
UnionFind uf(W); | |
_mem += sizeof(int) * W * 3; | |
// greedy | |
//int path_length = 0; | |
int _next[4] = { 10, 5, 10, 5 }; | |
// _next[0] = _next[2] = 10; // 1010 | |
// _next[1] = _next[3] = 5; // 0101 | |
for (int z=0; z<W; ) { | |
if (pq.empty()) break; | |
Distance d = -pq.top().first; | |
int v1 = pq.top().second.first, v2 = pq.top().second.second; | |
pq.pop(); | |
int p1 = M_of_MU(v1), h1 = U_of_MU(v1); | |
int p2 = M_of_MU(v2), h2 = U_of_MU(v2); | |
if (edge_to[p1].size() < 2 && edge_to[p2].size() < 2 | |
&& (used_h[p1] == 0 || (used_h[p1] & (1<<h1)) != 0) | |
&& (used_h[p2] == 0 || (used_h[p2] & (1<<h2)) != 0) | |
&& (uf.root(p1) != uf.root(p2) || z == W-1)) { | |
uf.unionSet(p1, p2); | |
// fprintf(stderr, " : [%d.%d - %d.%d]\n", p1,h1, p2,h2); | |
used_h[p1] = _next[h1]; | |
used_h[p2] = _next[h2]; | |
edge_to[p1].push_back(ii(h1, v2)); | |
edge_to[p2].push_back(ii(h2, v1)); | |
// path_length += d; | |
++z; | |
} | |
} | |
while (!pq.empty()) pq.pop(); | |
_mem -= (sizeof(Distance) + sizeof(int)*2) * W*(W-1)/2 * 16; | |
rep(i, W) { | |
if (edge_to[i].size() != 2) { | |
if (_verbose) { | |
fprintf(stderr, "!! edge_to[%d] = %d\n", i, (int)edge_to[i].size()); | |
} | |
// break; | |
} | |
assert(edge_to[i].size() == 2); | |
} | |
// find the route | |
task->path4.resize(W); | |
for (int i=0,p=M,h=0; i<W; ++i) { | |
for (int j=0; j<2; ++j) { | |
int h0 = edge_to[p][j].first; | |
if (h0 == -1) continue; | |
if (h0 == h) continue; | |
edge_to[p][j].first = -1; | |
int from = MU(p, h0); | |
// task->path4[2*i] = MU(p, h0); // ii(p, h0); | |
int _v = edge_to[p][j].second; | |
p = M_of_MU(_v); h = U_of_MU(_v); | |
// task->path4[2*i+1] = _v; // ii(p, h); | |
task->path4[i] = ii(from, _v); | |
break; | |
} | |
} | |
// cerr << task->path4 << endl; | |
// assert(task->path4.size() == W*2); | |
_mem += sizeof(int) * W*2; | |
//edge_to.clear(); | |
vector<vector<ii> >().swap(edge_to); | |
_mem -= sizeof(int) * W * 3; | |
//TIME_TO(t3,"<"+to_string(task->mode)+">find the route"); | |
//TIME_TO(t0,"<"+to_string(task->mode)+">tsp_greedy"); | |
} | |
inline bool is_valid_path(vector<int>& path, int W) { | |
if (path.size() != W) return false; | |
set<int> s; | |
rep(i, W) { | |
s.insert(path[i]); | |
} | |
return (s.size() == W); | |
} | |
inline bool is_valid_path4(vector<ii>& path4, int W) { | |
// cerr << "is_valid_path4(" << path4 << ", W=" << W << ")..." << endl; | |
set<int> s; | |
if (path4.size() != W) { | |
fprintf(stderr, "(|path4| = %lu) != (W = %d)\n", path4.size(), W); | |
return false; | |
} | |
rep(i, W-1) { | |
int pi_from = path4[i].first, pi_to = path4[i].second; | |
int pj_from = path4[i+1].first, pj_to = path4[i+1].second; | |
if (M_of_MU(pi_to) != M_of_MU(pj_from)) { | |
fprintf(stderr, "different vertex (%d != %d) at i=%d\n", | |
M_of_MU(pi_to), M_of_MU(pj_from), i); | |
return false; | |
} | |
int a = abs(U_of_MU(pi_to) - U_of_MU(pj_from)); | |
if (a == 3) a = 1; | |
if (a != 1) { | |
fprintf(stderr, "incompatible corner (%d x %d) at i=%d\n", | |
U_of_MU(pi_to), U_of_MU(pj_from), i); | |
return false; | |
} | |
} | |
rep(i, W) { | |
int pi_from = path4[i].first, pi_to = path4[i].second; | |
int i_from = M_of_MU(pi_from), i_to = M_of_MU(pi_to); | |
s.insert(i_from); | |
s.insert(i_to); | |
if (i_from < 0 || W <= i_from || i_to < 0 || W <= i_to) { | |
fprintf(stderr, "invalid index (%d, %d) at i=%d\n", i_from, i_to, i); | |
return false; | |
} | |
} | |
if (s.size() != W) { | |
fprintf(stderr, "path4 doesn't contain all the vertices (%d/%d)\n", | |
(int)s.size(), W); | |
return false; | |
} | |
return true; | |
} | |
int tsp4_rotate(Task *task, double qtx) { | |
int W = task->path4.size(); | |
int zmod = (W >= 1000) ? 2 : 3; | |
if (W < 100) zmod = 4; | |
if (W < 30) zmod = 1000; | |
int total = 0, count = 0, z = 0; | |
for (z=0; ; ++z) { | |
count = 0; | |
if ((z % zmod == zmod - 1) && overtime_check(qtx)) goto timeout; | |
for (int i=1; i<W-1; ++i) { | |
int prev_out = task->path4[i-1].first, here_in = task->path4[i-1].second; | |
int here_out = task->path4[i].first, next_in = task->path4[i].second; | |
Distance d_curr = task->distance_table4[prev_out][here_in] | |
+ task->distance_table4[here_out][next_in]; | |
Distance shortest = d_curr; | |
int shortest_at = -1; | |
int here_in_best, here_out_best; | |
int here_base = here_in & (~3); | |
rep(k, 8) { | |
int h = k % 4, m = (h + ((k & 4)? 3 : 1)) % 4; | |
int new_here_in = here_base | h; | |
Distance d_prev_here = task->distance_table4[prev_out][new_here_in]; | |
if (d_prev_here == SAME_POINT) continue; | |
int new_here_out = here_base | m; | |
Distance d_here_next = task->distance_table4[new_here_out][next_in]; | |
if (d_here_next == SAME_POINT) continue; | |
Distance d = d_prev_here + d_here_next; | |
if (d < shortest - 1e-7) { | |
shortest = d; | |
shortest_at = k; | |
here_in_best = new_here_in; | |
here_out_best = new_here_out; | |
} | |
} | |
if (shortest_at >= 0) { | |
// fprintf(stderr, "ROTATE4 at i=%d (%d %d) -> (%d %d) : %g < %g\n", i, here_in, here_out, here_in_best, here_out_best, shortest, d_curr); | |
task->path4[i-1].second = here_in_best; | |
task->path4[i].first = here_out_best; | |
++count; | |
} | |
} | |
if (count == 0) break; | |
total += count; | |
} | |
timeout: | |
done: | |
if (_verbose) { | |
fprintf(stderr, " tsp4_rotate(%g) : z=%d, total=%d\n", qtx, z, total); | |
} | |
return total; | |
} | |
inline void path4_rev(vector<ii>& v, int begin, int end) { | |
// end is not included | |
vector<ii> tmp; | |
for (int i=begin; i<end; ++i) { | |
tmp.push_back(iirev(v[i])); | |
} | |
reverse(all(tmp)); | |
for (int i=begin; i<end; ++i) v[i] = tmp[i - begin]; | |
} | |
void path4_rev_(vector<ii>::iterator begin, vector<ii>::iterator end) { | |
// end is not included | |
vector<ii> tmp; | |
for (vector<ii>::iterator it=begin; it!=end; ++it) { | |
tmp.push_back(iirev(*it)); | |
} | |
// reverse(tmp.begin(), tmp.end()); | |
auto jt = tmp.rbegin(); | |
for (vector<ii>::iterator it=begin; it!=end; ++it) { | |
*it = *jt++; | |
} | |
} | |
int tsp4_2_opt(Task *task, double qtx) { | |
assert(task->task_type == TASK_TSP4); | |
int W = task->path4.size(); | |
assert(task->distance_table4.size() == W*4); | |
int zmod = (W >= 1000) ? 2 : 3; | |
if (W < 100) zmod = 4; | |
if (W < 30) zmod = 1000; | |
int total = 0, count = 0, z = 0; | |
for (z=0; ; ++z) { | |
count = 0; | |
if ((z % zmod == zmod - 1) && overtime_check(qtx)) goto timeout; | |
for (int i=0; i<W-2; ++i) { | |
for (int j=i+2; j<W; ++j) { | |
int pi_from = task->path4[i].first, pi_to = task->path4[i].second; | |
Distance di = task->distance_table4[pi_from][pi_to]; | |
int pj_from = task->path4[j].first, pj_to = task->path4[j].second; | |
Distance dj = task->distance_table4[pj_from][pj_to]; | |
Distance d_before = di + dj; | |
Distance d_after_best = 2001 * 2; | |
int d_after_best_at = -1; | |
rep(k, 16) { | |
int pif = pi_from ^ ((k & 1)? 2 : 0), | |
pit = pi_to ^ ((k & 2)? 2 : 0), | |
pjf = pj_from ^ ((k & 4)? 2 : 0), | |
pjt = pj_to ^ ((k & 8)? 2 : 0); | |
Distance d1 = task->distance_table4[pif][pjf]; | |
if (d1 == SAME_POINT) continue; | |
Distance d2 = task->distance_table4[pit][pjt]; | |
if (d2 == SAME_POINT) continue; | |
Distance d = d1 + d2; | |
if (d < d_after_best) { | |
d_after_best = d; | |
d_after_best_at = k; | |
} | |
} | |
if (d_after_best < d_before) { | |
// fprintf(stderr, "DETECTED4<2>: %d -- %d (%d) delta=%g\n", i, j, min_d2_at, (di+dj)-min_d2); | |
// do replacement | |
int k = d_after_best_at; | |
int pif = pi_from ^ ((k & 1)? 2 : 0), | |
pit = pi_to ^ ((k & 2)? 2 : 0), | |
pjf = pj_from ^ ((k & 4)? 2 : 0), | |
pjt = pj_to ^ ((k & 8)? 2 : 0); | |
// (.. i-1) [i] (i+1 .. j-1) [j] (j+1 ..) | |
path4_rev(task->path4, i+1, j); | |
/* | |
vector<ii> tmp; | |
for (int u=i+1; u<j; ++u) { | |
ii pu = task->path4[u]; | |
tmp.push_back(ii(pu.second, pu.first)); | |
} | |
reverse(all(tmp)); | |
for (int u=i+1; u<j; ++u) task->path4[u] = tmp[u-(i+1)]; | |
*/ | |
task->path4[i] = ii(pif, pjf); | |
task->path4[j] = ii(pit, pjt); | |
// assert(is_valid_path4(task->path4, W)); | |
++count; | |
// break; | |
} | |
} | |
} | |
if (count == 0) goto done; | |
total += count; | |
} | |
timeout: | |
; | |
done: | |
if (_verbose) { | |
fprintf(stderr, " tsp4_2_opt(%g) : z=%d, total=%d\n", qtx, z, total); | |
} | |
return total; | |
} | |
int tsp4_or_opt_1(Task *task, double qtx) { | |
int W = task->path4.size(); | |
if (W < 3) return 0; | |
int zmod = (W >= 1000) ? 2 : 3; | |
if (W < 100) zmod = 4; | |
if (W < 30) zmod = 1000; | |
int total = 0, count = 0, z = 0; | |
for (z=0; ; ++z) { | |
count = 0; | |
if ((z % zmod == zmod - 1) && overtime_check(qtx)) goto timeout; | |
for (int i=1; i<W-1; ++i) { | |
int i_pre = i-1, i_post = i+1; | |
//// fprintf(stderr, "(%d)", i); | |
for (int j=2; j<W-2; ++j) { | |
int j0 = (i+j)%W, j1 = (j0+1)%W; | |
if (j0 == i_pre || j0 == i) continue; | |
if (j1 == i || j1 == i_post) continue; | |
int apre_out = task->path4[i_pre].first, a_in = task->path4[i_pre].second; | |
int a_out = task->path4[i].first, apost_in = task->path4[i].second; | |
Distance d_apre_a = task->distance_table4[apre_out][a_in]; | |
Distance d_a_apost = task->distance_table4[a_out][apost_in]; | |
// Distance da_before = d_apre_a + d_a_apost; | |
Distance d_apre_apost_best = 9999; | |
int d_apre_apost_best_at = -1; | |
rep(k, 4) { | |
int new_apre_out = apre_out ^ ((k & 1)? 2 : 0); | |
int new_apost_in = apost_in ^ ((k & 2)? 2 : 0); | |
Distance d = task->distance_table4[new_apre_out][new_apost_in]; | |
if (d == SAME_POINT) continue; | |
if (d < d_apre_apost_best) { | |
d_apre_apost_best = d; | |
d_apre_apost_best_at = k; | |
} | |
} | |
int b0_out = task->path4[j0].first, b1_in = task->path4[j0].second; | |
Distance d_b0_b1 = task->distance_table4[b0_out][b1_in]; | |
// Distance db_before = d_b0_b1; | |
Distance z_before = (d_apre_a + d_a_apost) + d_b0_b1; | |
Distance d_b0_a_b1_best = 9999; | |
int d_b0_a_b1_best_at = -1; | |
rep(k, 32) { | |
int new_b0_out = b0_out ^ ((k & 8)? 2 : 0), | |
new_b1_in = b1_in ^ ((k & 16)? 2 : 0); | |
int _base = a_out & ~3; | |
int l = k % 4; | |
int m = (k & 4)? 3 : 1; | |
int new_a_in = _base | l; | |
int new_a_out = _base | ((l+m)%4); | |
// (p0 .. q0), (q1 .. p1) | |
Distance d_new_b0_a = task->distance_table4[new_b0_out][new_a_in]; | |
if (d_new_b0_a == SAME_POINT) continue; | |
Distance d_new_a_b1 = task->distance_table4[new_a_out][new_b1_in]; | |
if (d_new_b0_a == d_new_a_b1) continue; | |
Distance d = d_new_b0_a + d_new_a_b1; | |
if (d < d_b0_a_b1_best) { | |
d_b0_a_b1_best = d; | |
d_b0_a_b1_best_at = k; | |
} | |
} | |
// fprintf(stderr, " : 4<or1> (%g + %g) + %g | %g + (%g)\n", d_apre_a, d_a_apost, d_b0_b1, d_apre_apost_best, d_b0_a_b1_best); | |
Distance z_after = d_apre_apost_best + d_b0_a_b1_best; | |
if (z_after < z_before) { | |
// fprintf(stderr, "DETECTED4<or1> i=%d j=%d k=%d %d\n", i, j, d_apre_apost_best_at, d_b0_a_b1_best_at); | |
// do replacement | |
// (i_pre, i) (i, i_post) -> (i_pre*, i_post*) | |
// (j0, j1) -> (j0*, i) (i, j1*) | |
int new_apre_out = apre_out ^ ((d_apre_apost_best_at & 1)? 2 : 0); | |
int new_apost_in = apost_in ^ ((d_apre_apost_best_at & 2)? 2 : 0); | |
int new_b0_out = b0_out ^ ((d_b0_a_b1_best_at & 8)? 2 : 0), | |
new_b1_in = b1_in ^ ((d_b0_a_b1_best_at & 16)? 2 : 0); | |
int _base = a_out & ~3; | |
int l = d_b0_a_b1_best_at % 4; | |
int m = (d_b0_a_b1_best_at & 4)? 3 : 1; | |
int new_a_in = _base | l; | |
int new_a_out = _base | ((l+m)%4); | |
/* | |
fprintf(stderr, " : (%d, %d) (%d, %d) -> (%d, %d)\n", | |
apre_out, a_in, a_out, apost_in, | |
new_apre_out, new_apost_in); | |
fprintf(stderr, " : (%d, %d) -> (%d, %d) (%d, %d)\n", | |
b0_out, b1_in, | |
new_b0_out, new_a_in, new_a_out, new_b1_in); | |
*/ | |
if (i < j0) { | |
for (int k=i; k<j0; ++k) { | |
task->path4[k] = task->path4[k+1]; | |
} | |
task->path4[j0-1] = ii(new_b0_out, new_a_in); | |
task->path4[i_pre] = ii(new_apre_out, new_apost_in); | |
task->path4[j0] = ii(new_a_out, new_b1_in); | |
} else { // j0 < i0 | |
for (int k=i-1; k>j0+1; --k) { | |
task->path4[k] = task->path4[k-1]; | |
} | |
task->path4[j0] = ii(new_b0_out, new_a_in); | |
task->path4[i_pre+1] = ii(new_apre_out, new_apost_in); | |
task->path4[j0+1] = ii(new_a_out, new_b1_in); | |
} | |
// assert(is_valid_path4(task->path4, W)); | |
++count; | |
// break; | |
} | |
} | |
} | |
if (count == 0) goto done; | |
total += count; | |
} | |
timeout: | |
; | |
done: | |
if (_verbose) { | |
fprintf(stderr, " tsp4_or_opt_1(%g) : z=%d, total=%d\n", qtx, z, total); | |
} | |
return total; | |
} | |
inline Distance path4_edge_length(Task *task, int ix) { | |
int p1_out = task->path4[ix].first, p2_in = task->path4[ix].second; | |
Distance d = task->distance_table4[p1_out][p2_in]; | |
return d; | |
} | |
Distance shortest4(Task *task, int& p1_out, int& p2_in) { | |
Distance d_best = 9999; | |
int p1_out_best, p2_in_best; | |
rep(k, 4) { | |
int p1_out_k = p1_out ^ ((k & 1)? 2 : 0); | |
int p2_in_k = p2_in ^ ((k & 2)? 2 : 0); | |
Distance d = task->distance_table4[p1_out_k][p2_in_k]; | |
if (d == SAME_POINT) continue; | |
if (d < d_best) { | |
// best_at = k; | |
p1_out_best = p1_out_k; | |
p2_in_best = p2_in_k; | |
d_best = d; | |
} | |
} | |
p1_out = p1_out_best; | |
p2_in = p2_in_best; | |
return d_best; | |
} | |
inline int MU_next(int mu, bool which) { | |
// return mu; | |
int m = M_of_MU(mu), u = U_of_MU(mu); | |
if (which) { | |
return MU(m, (u+1)%4); | |
} else { | |
return MU(m, (u+3)%4); | |
} | |
} | |
int tsp4_or_opt_n(Task *task, int nmin, int nmax, double qtx) { | |
int W = task->path4.size(); | |
if (W < 3) return 0; | |
int zmod = (W >= 1000) ? 2 : 3; | |
if (W < 100) zmod = 4; | |
if (W < 30) zmod = 1000; | |
int total = 0, count = 0, z = 0; | |
for (z=0; ; ++z) { | |
count = 0; | |
if ((z % zmod == zmod - 1) && overtime_check(qtx)) goto timeout; | |
for (int i=0; i<W; ++i) { | |
int ipre = (i-1 +W)%W; | |
/* | |
int i_pre = (i-1 +W)%W, i_post = (i+1)%W; | |
//int i_first = i, i_last = i; | |
int apre_out = task->path4[i_pre].first, a0_in = task->path4[i_pre].second; | |
int a0_out = task->path4[i0].first, a1_in = task->path4[i0].second; | |
int a_last = a0; | |
int a_post = a0; // task->path[i0 % W]; | |
Distance d_apre_a0 = task->distance_table4[apre_out][a0_in]; // fixed | |
Distance d_a0_alast = 0; | |
*/ | |
int apre_out = task->path4[ipre].first, a_in = task->path4[ipre].second; | |
vector<ii> subpath; | |
Distance subpath_length = 0; | |
for (int n=1; n<=nmax; ++n) { // n=頂点の数 | |
int ilast = (i+n-1)%W; | |
if (n >= W-2) break; | |
// i-1 [i .. i+n-1] i+n ... { j j+1 } ... | |
// i-1 i+n .... { j [i ... i+n-1] j+1 } ... | |
int alast_out = task->path4[ilast].first, apost_in = task->path4[ilast].second; | |
ii edge_n = task->path4[(i+n-1)%W]; | |
subpath.push_back(edge_n); | |
Distance d_this_edge = path4_edge_length(task, (i+n-1)%W); | |
// i_pre: [i-1 i) -> [i-1 i+n) | |
// i_pre: (apre_out a_in) -> (apre_out an_in) | |
// i+n-1: [i+n-1 i+n) -> [i+n-1 j+1) | |
// ilast: (alast_out an_in) -> (alast_out b1_in) | |
// j: [j j+1) -> [j i) | |
// j: (b0_out b1_in) -> (b0_out a_in) | |
for (int j=i+n; j<i+W-1; ++j) { | |
// j=i+W-2のとき j0=i-2, j1=i-1=ipre | |
int j0 = j%W, j1 = (j+1)%W; | |
int b0_out = task->path4[j0].first, b1_in = task->path4[j0].second; | |
Distance d_apre_a = path4_edge_length(task, ipre); // task->distance_table4[apre_out][a_in] | |
Distance d_alast_apost = path4_edge_length(task, ilast); // task->distance_table4[alast_out][apost_in]; | |
Distance d_b0_b1 = path4_edge_length(task, j0); // task->distance_table4[b0_out][b1_in]; | |
Distance z_before = (d_apre_a + subpath_length + d_alast_apost) + d_b0_b1; | |
// fprintf(stderr, ": z_before = (%g + %g + %g) + %g\n", d_apre_a, subpath_length, d_alast_apost, d_b0_b1); | |
int apre_out_ = apre_out, apost_in_ = apost_in; | |
Distance d_apre_apost = shortest4(task, apre_out_, apost_in_); | |
int a_in_ = a_in, alast_out_ = alast_out; | |
int b0_out_ = b0_out, b1_in_ = b1_in; | |
Distance d_b0_a = shortest4(task, b0_out_, a_in_); | |
Distance d_alast_b1 = shortest4(task, alast_out_, b1_in_); | |
Distance z_after = d_apre_apost + (d_b0_a + subpath_length + d_alast_b1); | |
int a_out_ = a_in, alast_in_ = alast_out; | |
int b0_out_REV = b0_out, b1_in_REV = b1_in; | |
Distance d_b0_alast = shortest4(task, b0_out_REV, alast_in_); | |
Distance d_a_b1 = shortest4(task, a_out_, b1_in_REV); | |
Distance z_after_REV = d_apre_apost + (d_b0_alast + subpath_length + d_a_b1); | |
if (z_after_REV < z_after) goto rev; | |
if (z_after < z_before - 1e-6) { | |
// fprintf(stderr, "DETECTED4<or-n> W=%d i=%d n=%d j=%d (%g < %g)\n", W, i,n,j, z_after,z_before); | |
/* | |
cerr << " path4:" << task->path4 << endl; | |
cerr << " subpath:" << subpath << endl; | |
cerr << " ::" << ii(apre_out_, apost_in_) << " / " << ii(b0_out_, a_in_) << " / " << ii(alast_out_, b1_in_) << endl; | |
*/ | |
if (i < j0) { // i < i+n < j0 | |
for (int k=i; k<j0+1-n; ++k) { | |
task->path4[k] = task->path4[k+n]; | |
} | |
for (int k=j0+1-n,l=0; l<n; ++k,++l) { | |
task->path4[k] = subpath[l]; | |
} | |
task->path4[j0-n] = ii(b0_out_, a_in_); | |
task->path4[j0] = ii(alast_out_, b1_in_); | |
task->path4[ipre] = ii(apre_out_, apost_in_); | |
} else { // j0 < i | |
if (i+n < W) { | |
for (int k=i+n-1; k>j0+n; --k) { | |
task->path4[k%W] = task->path4[(k-n)%W]; | |
} | |
for (int k=j0+1,l=0; l<n; ++k,++l) { | |
task->path4[k%W] = subpath[l]; | |
} | |
// task->path4[j0+1 + n-1] = // | |
task->path4[j0] = ii(b0_out_, a_in_); | |
task->path4[j0+n] = ii(alast_out_, b1_in_); | |
task->path4[(ipre+n)%W] = ii(apre_out_, apost_in_); | |
} else { | |
int delta = i + n - W; | |
// n - delta = W - i | |
assert(j0-delta >= 0); | |
for (int k=0; k<j0-delta; ++k) { | |
task->path4[k] = task->path4[k+delta]; | |
} | |
assert(j0-delta-1+delta < j0-delta+n+1-(n-delta)); | |
for (int k=W-1; k>j0+n-delta; --k) { | |
task->path4[k] = task->path4[k-(n-delta)]; | |
} | |
task->path4[W-1] = ii(apre_out_, apost_in_); | |
// j0+(n-delta)+1-(n-delta) = j0+1 | |
task->path4[j0-delta] = ii(b0_out_, a_in_); | |
for (int k=j0+1-delta,l=0; l<n; ++k,++l) { | |
task->path4[k] = subpath[l]; | |
} | |
task->path4[j0+n-delta] = ii(alast_out_, b1_in_); | |
// j0+(n-delta) = j0+W-i = W-(i-j0) | |
} | |
} | |
// assert(is_valid_path4(task->path4, W)); | |
++count; | |
goto found_one; | |
} | |
rev: | |
; | |
if (z_after_REV < z_before - 1e-6) { | |
// fprintf(stderr, "DETECTED4<or-n>REV W=%d i=%d n=%d j=%d (%g < %g)\n", W, i,n,j, z_after,z_before); | |
/* | |
cerr << " path4:" << task->path4 << endl; | |
cerr << " subpath:" << subpath << endl; | |
cerr << " ::" << ii(apre_out_, apost_in_) << " / " << ii(b0_out_, a_in_) << " / " << ii(alast_out_, b1_in_) << endl; | |
*/ | |
if (i < j0) { | |
for (int k=i; k<j0+1-n; ++k) { | |
task->path4[k] = task->path4[k+n]; | |
} | |
for (int k=j0+1-n,l=n-2; l>=0; ++k,--l) { | |
task->path4[k] = iirev(subpath[l]); | |
} | |
// task->path4[j0+1-n + n-1] = // | |
task->path4[j0-n] = ii(b0_out_REV, alast_in_); | |
task->path4[j0] = ii(a_out_, b1_in_REV); | |
task->path4[ipre] = ii(apre_out_, apost_in_); | |
} else { // j0 < i | |
if (i+n < W) { | |
for (int k=i+n-1; k>j0+n; --k) { | |
task->path4[k%W] = task->path4[(k-n)%W]; | |
} | |
for (int k=j0+1,l=n-2; l>=0; ++k,--l) { | |
task->path4[k%W] = iirev(subpath[l]); | |
} | |
// task->path4[j0+1 + n-1] = // | |
task->path4[j0] = ii(b0_out_REV, alast_in_); | |
task->path4[j0+n] = ii(a_out_, b1_in_REV); | |
task->path4[(ipre+n)%W] = ii(apre_out_, apost_in_); | |
} else { | |
int delta = i + n - W; | |
// n - delta = W - i | |
assert(j0-delta >= 0); | |
for (int k=0; k<j0-delta; ++k) { | |
task->path4[k] = task->path4[k+delta]; | |
} | |
assert(j0-delta-1+delta < j0-delta+n+1-(n-delta)); | |
for (int k=W-1; k>j0+n-delta; --k) { | |
task->path4[k] = task->path4[k-(n-delta)]; | |
} | |
task->path4[W-1] = ii(apre_out_, apost_in_); | |
// j0+(n-delta)+1-(n-delta) = j0+1 | |
task->path4[j0-delta] = ii(b0_out_REV, alast_in_); | |
for (int k=j0+1-delta,l=n-2; l>=0; ++k,--l) { | |
task->path4[k] = iirev(subpath[l]); | |
} | |
task->path4[j0+n-delta] = ii(a_out_, b1_in_REV); | |
// j0+(n-delta) = j0+W-i = W-(i-j0) | |
} | |
} | |
// assert(is_valid_path4(task->path4, W)); | |
++count; | |
goto found_one; | |
} | |
} // next j | |
subpath_length += d_this_edge; | |
} // next n | |
// ++count; | |
found_one: | |
; | |
} // next i | |
if (count == 0) goto done; | |
total += count; | |
} | |
timeout: | |
; | |
done: | |
if (_verbose) { | |
fprintf(stderr, " tsp4_or_opt_n(%g) : z=%d, total=%d\n", qtx, z, total); | |
} | |
return total; | |
} | |
int tsp_2_opt(Task *task, double qtx) { | |
int mode = task->mode; | |
//TIME_FROM(t0); | |
int W = task->path.size(); | |
assert(task->distance_table.size() == W); | |
int zmod = (W >= 1000) ? 2 : 3; | |
if (W < 100) zmod = 4; | |
if (W < 30) zmod = 1000; | |
int total = 0, count = 0, z = 0; | |
#ifdef DO_SHUFFLE | |
vector<int> x(W-2); rep(i, W-2) x[i] = i; | |
#endif | |
for (z=0; ; ++z) { | |
count = 0; | |
if ((z % zmod == zmod - 1) && overtime_check(qtx)) goto timeout; | |
// for (int i0=0; i0<W-2; ++i0) { | |
for (int i0=0; i0<W; ++i0) { | |
// for (int _i0=0; _i0<W; ++_i0) { | |
// int i0 = x[_i0]; | |
int i1 = (i0+1) % W; | |
// int found_here = 0; | |
//for (int j0=(i1+1)%W; j0<W; ++j0) {// ++j0) { | |
// for (int j0=i1+1; j0<W; ++j0) { | |
#ifdef DO_SHUFFLE | |
if (task->shuffle > 0) shuffle(x); | |
rep(_j, W-2) { | |
int j0 = (i1+1+x[_j])%W; // , j1 = (j0+1)%W; | |
#else | |
rep(_j, W-2) { | |
int j0 = (i1+1+_j)%W; // , j1 = (j0+1)%W; | |
#endif | |
bool found_one = false; | |
// if (overtime_check(qtx)) goto timeout;//// | |
int j1 = (j0+1) % W; | |
if (i0 == 0 && j1 == 0) continue; | |
int a0 = task->path[i0], a1 = task->path[i1]; | |
int b0 = task->path[j0], b1 = task->path[j1]; | |
// | |
Distance d_a0_a1 = task->distance_table[a0][a1]; | |
Distance d_b0_b1 = task->distance_table[b0][b1]; | |
Distance d_a0_b0 = task->distance_table[a0][b0]; | |
Distance d_a1_b1 = task->distance_table[a1][b1]; | |
Distance z_before = d_a0_a1 + d_b0_b1; | |
Distance z_after = d_a0_b0 + d_a1_b1; | |
if (z_after < z_before) { | |
// fprintf(stderr, "DETECTED (%d-%d) x (%d-%d)\n", i,i1, j,j1); | |
if (i0 < j0) { | |
// [0 .. i0] [i1 .s. j0] [j1 .. | |
for (int u=i1,v=j0; u<v; ++u,--v) { | |
swap(task->path[u], task->path[v]); | |
} | |
// reverse(task->path.begin()+i1, task->path.begin()+j0+1); | |
} else { | |
// vector<int> _tmp(all(task->path)); | |
// int w_i1_W = W - i1, w_0_j1 = j1; | |
// .. j0] [j1 .. i0] [i1 .s. | |
// j0=0(i1), j0-1=i1+1, ... 0=i1+j0 | |
for (int u=i1,v=j0+W; u<v; ++u,--v) { | |
swap(task->path[u%W], task->path[v%W]); | |
} | |
} | |
#ifdef CHECK_PATH_VALIDITY | |
assert(is_valid_path(task->path, W)); | |
#endif | |
found_one = true; | |
// break; | |
} | |
/* | |
rep(i, W) { | |
int a0 = task->path[i], a1 = task->path[(i+1)%W]; | |
assert(ds[i] == task->distance_table[a0][a1]); | |
} | |
*/ | |
if (found_one) ++count; | |
} // next j0 | |
} // next i0 | |
if (count == 0) { | |
goto done; | |
} | |
total += count; | |
} // next z | |
timeout: | |
if (_verbose) { | |
// fprintf(stderr, " // overtime = %gmsec\n", _otdelay*1000); | |
} | |
done: | |
if (_verbose) { | |
fprintf(stderr, " tsp_2_opt(%g) : z=%d, total=%d\n", qtx, z, total); | |
} | |
//TIME_TO(t0,"<"+to_string(task->mode)+">2-opt, total="+to_string(total)); | |
return total; | |
} | |
int tsp_or_opt_1(Task *task, double qtx) { | |
int mode = task->mode; | |
//TIME_FROM(t0); | |
if (_verbose) { | |
// fprintf(stderr, "%% tsp_or_opt_1(task)... W=%d\n", (int)task->path.size()); | |
} | |
int W = task->path.size(); | |
if (W < 3) return 0; | |
assert(task->distance_table.size() == W && task->distance_table[0].size() == W); | |
int zmod = (W >= 1000) ? 2 : 3; | |
if (W < 100) zmod = 4; | |
if (W < 30) zmod = 1000; | |
int total = 0, count = 0, z = 0; | |
#ifdef DO_SHUFFLE | |
vector<int> x(W); rep(i, W) x[i] = i; | |
#endif | |
for (z=0; ; ++z) { | |
count = 0; | |
if ((z % zmod == zmod - 1) && overtime_check(qtx)) goto timeout; | |
rep(i, W) { | |
int i_pre = (i-1 +W) % W, i_post = (i+1) % W; | |
// int a_pre = path[i_pre], a = path[i], a_post = path[i_post]; | |
#ifdef DO_SHUFFLE | |
if (task->shuffle > 0) shuffle(x); | |
rep(_j0, W) { | |
int j0 = x[_j0]; | |
#else | |
rep(j0, W) { | |
#endif | |
// if (overtime_check(qtx)) goto timeout; | |
int j1 = (j0+1) % W; | |
if (j0 == i || j1 == i) continue; | |
int a_pre = task->path[i_pre], a = task->path[i], a_post = task->path[i_post]; | |
int b0 = task->path[j0], b1 = task->path[j1]; | |
// | |
Distance d_apre_a = task->distance_table[a_pre][a]; | |
Distance d_a_apost = task->distance_table[a][a_post]; | |
Distance d_apre_apost = task->distance_table[a_pre][a_post]; | |
Distance d_b0_b1 = task->distance_table[b0][b1]; | |
Distance d_b0_a = task->distance_table[b0][a]; | |
Distance d_a_b1 = task->distance_table[a][b1]; | |
Distance z_before = (d_apre_a + d_a_apost) + d_b0_b1; | |
Distance z_after = d_apre_apost + (d_b0_a + d_a_b1); | |
if (z_after < z_before) { | |
//fprintf(stderr, "DETECTED (%d-<%d>-%d) => (%d-%d)\n", i0,i,i1, j,j1); | |
if (i < j1) { | |
// [i0] <--- [j0] a0 a1 [j1] | |
for (int k=i; k<j1-1; ++k) | |
task->path[k] = task->path[k+1]; | |
task->path[j1-1] = a; | |
} else { | |
// [j0] a0 a1 [j1] ---> [i0] | |
for (int k=i; k<j1-1+W; ++k) | |
task->path[k%W] = task->path[(k+1)%W]; | |
task->path[(j1-1+W)%W] = a; | |
} | |
#ifdef CHECK_PATH_VALIDITY | |
assert(is_valid_path(task->path, W)); | |
#endif | |
++count; | |
// break; | |
} | |
} | |
} | |
if (count == 0) { | |
goto done; | |
} | |
total += count; | |
} // next z | |
timeout: | |
// total += count; | |
done: | |
if (_verbose) { | |
fprintf(stderr, " tsp_or_opt_1(%g) : z=%d, total=%d\n", qtx, z, total); | |
} | |
//TIME_TO(t0,"<"+to_string(task->mode)+">or-opt1, total="+to_string(total)); | |
return total; | |
} | |
int tsp_or_opt_2(Task *task, double qtx) { | |
int mode = task->mode; | |
//TIME_FROM(t0); | |
if (_verbose) { | |
// fprintf(stderr, "%% tsp_or_opt_2(task)... W=%d\n", (int)task->path.size()); | |
} | |
int W = task->path.size(); | |
if (W < 6) return 0; | |
assert(task->distance_table.size() == W); | |
int zmod = (W >= 1000) ? 2 : 3; | |
if (W < 100) zmod = 4; | |
if (W < 30) zmod = 1000; | |
int total = 0, count = 0, z = 0; | |
#ifdef DO_SHUFFLE | |
vector<int> x(W); rep(i, W) x[i] = i; | |
#endif | |
for (z=0; ; ++z) { | |
count = 0; | |
if ((z % zmod == zmod - 1) && overtime_check(qtx)) goto timeout; | |
for (int i0=0; i0<W; ++i0) { | |
// for (int _i0=0; _i0<W; ++_i0) { | |
// int i0 = x[_i0]; | |
// for (int i0=0; i0<W-2; ++i0) { | |
// for (int i0=0; i0<W; ++i0) { ///// | |
int i_pre = (i0-1 +W)%W, i1 = (i0+1)%W, i_post = (i1+1)%W; | |
#ifdef DO_SHUFFLE | |
if (task->shuffle > 0) shuffle(x); | |
rep(_j0, W) { | |
int j0 = x[_j0]; | |
#else | |
rep(j0, W) { | |
#endif | |
// if (overtime_check(qtx)) goto timeout; | |
int j1 = (j0+1) % W; | |
if (j0 == i0 || j0 == i1 || j1 == i0 || j1 == i1) continue; | |
//rep(i, W) assert(0 <= task->path[i] && task->path[i] < W); | |
int a_pre = task->path[i_pre], a0 = task->path[i0], a1 = task->path[i1], a_post = task->path[i_post]; | |
int b0 = task->path[j0], b1 = task->path[j1]; | |
// | |
Distance d_apre_a0 = task->distance_table[a_pre][a0]; | |
Distance d_a0_a1 = task->distance_table[a0][a1], d_a1_a0 = d_a0_a1; | |
Distance d_a1_apost = task->distance_table[a1][a_post]; | |
Distance d_apre_apost = task->distance_table[a_pre][a_post]; | |
Distance d_b0_b1 = task->distance_table[b0][b1]; | |
Distance d_b0_a0 = task->distance_table[b0][a0]; | |
Distance d_b0_a1 = task->distance_table[b0][a1]; | |
Distance d_a0_b1 = task->distance_table[a0][b1]; | |
Distance d_a1_b1 = task->distance_table[a1][b1]; | |
Distance z_before = (d_apre_a0 + d_a0_a1 + d_a1_apost) + d_b0_b1; | |
Distance z_after1 = d_apre_apost + (d_b0_a0 + d_a0_a1 + d_a1_b1); | |
Distance z_after2 = d_apre_apost + (d_b0_a1 + d_a1_a0 + d_a0_b1); | |
if (z_after1 < z_before) { | |
if (_verbose) { | |
// fprintf(stderr, "DETECTED (a) (%d'%d.%d'%d) => (%d'%d)\n", i_pre,i0,i1,i_post, j0,j1); | |
} | |
// inserting {a0, a1} between j0.j1 | |
if (i0 < j1) { | |
// [i0] <--- [j0] a0 a1 [j1] | |
for (int k=i0; k<j1-2; ++k) | |
task->path[k] = task->path[k+2]; | |
task->path[j1-2] = a0; | |
task->path[j1-1] = a1; | |
} else { | |
// [j0] a0 a1 [j1] ---> [i0] | |
for (int k=i0; k<j1-2+W; ++k) | |
task->path[k%W] = task->path[(k+2)%W]; | |
task->path[(j1-2+W)%W] = a0; | |
task->path[(j1-1+W)%W] = a1; | |
} | |
#ifdef CHECK_PATH_VALIDITY | |
assert(is_valid_path(task->path, W)); | |
#endif | |
++count; | |
// break; | |
} else if (z_after2 < z_before) { | |
if (i0 < j1) { | |
// [i0] <--- [j0] a0 a1 [j1] | |
for (int k=i0; k<j1-2; ++k) | |
task->path[k] = task->path[k+2]; | |
task->path[j1-2] = a1; | |
task->path[j1-1] = a0; | |
} else { | |
// [j0] a0 a1 [j1] ---> [i0] | |
for (int k=i0; k<j1-2+W; ++k) | |
task->path[k%W] = task->path[(k+2)%W]; | |
task->path[(j1-2+W)%W] = a1; | |
task->path[(j1-1+W)%W] = a0; | |
} | |
/* | |
if (i0 < j1) { | |
task->path.insert(task->path.begin()+j1, a0); | |
task->path.insert(task->path.begin()+j1, a1); | |
task->path.erase(task->path.begin()+i0, task->path.begin()+i0+2); | |
} else { | |
task->path.erase(task->path.begin()+i0, task->path.begin()+i0+2); | |
task->path.insert(task->path.begin()+j1, a0); | |
task->path.insert(task->path.begin()+j1, a1); | |
} | |
*/ | |
#ifdef CHECK_PATH_VALIDITY | |
assert(is_valid_path(task->path, W)); | |
#endif | |
++count; | |
// break; | |
} | |
} | |
} | |
// assert(is_valid_path(task->path, W)); | |
if (count == 0) { | |
goto done; | |
} | |
total += count; | |
} | |
timeout: | |
// total += count; | |
done: | |
if (_verbose) { | |
fprintf(stderr, " tsp_or_opt_2(%g) : z=%d, total=%d\n", qtx, z, total); | |
} | |
//TIME_TO(t0,"<"+to_string(task->mode)+">or-opt#2, total="+to_string(total)); | |
return total; | |
} | |
int tsp_or_opt_n(Task *task, int nmin, int nmax, double qtx) { | |
int mode = task->mode; | |
//TIME_FROM(t0); | |
if (_verbose) { | |
// fprintf(stderr, "%% tsp_or_opt_n(task, nmin=%d, nmax=%d)... W=%d\n", nmin, nmax, (int)task->path.size()); | |
} | |
int W = task->path.size(); | |
// nmax = min(nmax, W/2); | |
// if (W < nmax) return 0; | |
assert(task->distance_table.size() == W); | |
int zmod = (W >= 1000) ? 2 : 3; | |
if (W < 100) zmod = 4; | |
if (W < 30) zmod = 1000; | |
int total = 0, count = 0, z = 0; | |
for (z=0; ; ++z) { | |
count = 0; | |
if ((z % zmod == zmod - 1) && overtime_check(qtx)) goto timeout; | |
#if 0 | |
vector<int> x(W); rep(i, W) x[i] = i; shuffle(x); | |
for (int _i0=0; _i0<W; ++_i0) { | |
int i0 = x[_i0]; | |
#else | |
for (int i0=0; i0<W; ++i0) { | |
#endif | |
// @pre(i-1) . { i, ... i+(n-1) } . post(i+n) | |
// a_pre, (a0 ... a_last), a_post | |
int a_pre = task->path[(i0-1 +W)%W]; | |
int a0 = task->path[i0], a_last = a0; | |
int a_post = a0; // task->path[i0 % W]; | |
Distance d_apre_a0 = task->distance_table[a_pre][a0]; // fixed | |
Distance d_a0_alast = 0; | |
// double d_alast_apost = task->distance_table[a0][a_post]; // | |
vector<int> ai; | |
// Distance d_apre_a1 = task->distance_table[a_pre][a1]; | |
for (int n=1; n<=nmax; ++n) { | |
if (n >= W-2) break; | |
// int a_next = a_post; // task->path[(i+n)%W]; | |
ai.push_back(a_post); | |
d_a0_alast += task->distance_table[a_last][a_post]; | |
/* | |
if (n == 1) assert(d_a0_alast == 0); | |
if (n == 2) assert(d_a0_alast == task->distance_table[task->path[i0]][task->path[(i0+1)%W]]); | |
if (n == 3) assert(d_a0_alast == task->distance_table[task->path[i0]][task->path[(i0+1)%W]] + task->distance_table[task->path[(i0+1)%W]][task->path[(i0+2)%W]]); | |
*/ | |
// int i_last = i0+(n-1), i_post = i0+n; | |
a_last = a_post; // assert(a_last == task->path[i_last%W]); | |
a_post = task->path[(i0+n)%W]; | |
// assert(a_last != a_post); | |
Distance d_alast_apost = task->distance_table[a_last][a_post]; | |
Distance d_apre_apost = task->distance_table[a_pre][a_post]; | |
// before: (d_apre_a0 + d_a0_alast + d_alast_apost) + d_b0_b1 | |
// after<1> : d_apre_apost + (d_b0_a0 + d_alast_b1) | |
// after<2> : d_apre_apost + (d_b0_alast + d_a0_b1) | |
if (n < nmin) continue; /// | |
#if 0 | |
#ifdef DO_SHUFFLE | |
vector<int> x; | |
for (int k=i0+n+1; k<i0+W-1; ++k) x.push_back(k%W); | |
// rep(i, W) x[i] = i; | |
if (task->shuffle > 0) shuffle(x); | |
for (int _j0=0; _j0<W-n-2; ++_j0) { | |
int j0 = x[_j0], j1 = (j0+1)%W; | |
#endif | |
#else | |
for (int _j0=i0+n+1; _j0<i0+W-1; ++_j0) { | |
int j0 = _j0%W, j1 = (j0+1)%W; | |
#endif | |
int b0 = task->path[j0], b1 = task->path[j1]; | |
Distance d_b0_b1 = task->distance_table[b0][b1]; | |
Distance z_before = (d_apre_a0 + d_a0_alast + d_alast_apost) + d_b0_b1; | |
Distance d_b0_a0 = task->distance_table[b0][a0]; | |
Distance d_alast_b1 = task->distance_table[a_last][b1]; | |
Distance z_after1 = d_apre_apost + (d_b0_a0 + d_a0_alast + d_alast_b1); | |
Distance d_b0_alast = task->distance_table[b0][a_last]; | |
Distance d_a0_b1 = task->distance_table[a0][b1]; | |
Distance z_after2 = d_apre_apost + (d_b0_alast + d_a0_alast + d_a0_b1); | |
if (z_after1 < z_before) { | |
if (_verbose) { | |
// fprintf(stderr, "DETECTED n=%d (a) (%d'[%d..%d]'%d) => (%d'%d) ; W=%d\n", n, i0-1,i0,i0+n-1,i0+n, j0,j1, W); | |
} | |
// assert(is_valid_path(task->path, W)); | |
if (i0 < j1) { | |
// [i0] <--- [j0] a0 a1 [j1] | |
for (int k=i0; k<j1-n; ++k) | |
task->path[k] = task->path[k+n]; | |
for (int k=0; k<n; ++k) | |
task->path[j1-n+k] = ai[k]; | |
} else { | |
// j1 < i0 | |
// [j0] a0 a1 [j1] ---> [i0] ... [i0+n] | |
for (int k=i0+n-1; k>=j1+n; --k) | |
task->path[(k+W)%W] = task->path[(k-n+W)%W]; | |
for (int k=0; k<n; ++k) | |
task->path[(j1+k)%W] = ai[k]; | |
} | |
#if 0 | |
if (i0+n > W) { // i0 < W|0 < j1 < i0 | |
task->path.erase(task->path.begin()+i0, task->path.end()); | |
task->path.insert(task->path.begin()+j1, all(ai)); | |
task->path.erase(task->path.begin(), task->path.begin()+(i0+n-W)); | |
} else { // 0 < j1 <= i0 < ilast <= W | |
task->path.erase(task->path.begin()+i0, task->path.begin()+i0+n); | |
task->path.insert(task->path.begin()+j1, all(ai)); | |
} | |
#endif | |
// assert(is_valid_path(task->path, W)); | |
++count; | |
goto found_one; | |
} else if (z_after2 < z_before) { | |
if (_verbose) { | |
// fprintf(stderr, "DETECTED n=%d (b) (%d'[%d..%d]'%d) => (%d'%d) ; W=%d\n", n, i0-1,i0,i0+n-1,i0+n, j0,j1, W); | |
} | |
if (i0 < j1) { | |
// [i0] <--- [j0] a0 a1 [j1] | |
for (int k=i0; k<j1-n; ++k) | |
task->path[k] = task->path[k+n]; | |
for (int k=0; k<n; ++k) | |
task->path[j1-n+k] = ai[n-1-k]; | |
} else { | |
// j1 < i0 | |
// [j0] a0 a1 [j1] ---> [i0] ... [i0+n] | |
for (int k=i0+n-1; k>=j1+n; --k) | |
task->path[(k+W)%W] = task->path[(k-n+W)%W]; | |
for (int k=0; k<n; ++k) | |
task->path[(j1+k)%W] = ai[n-1-k]; | |
} | |
#if 0 | |
if (i0 < j1) { // j0=i0+[n+1..W-1),, j1=i0+[n+2..W) | |
task->path.insert(task->path.begin()+j1, rall(ai)); | |
assert(i0+n < W); | |
task->path.erase(task->path.begin()+i0, task->path.begin()+i0+n); | |
} else { // j1 < i0 < ilast, or ilast < j1 < i0 | |
int rem = i0+n - W; | |
if (rem > 0) { // i0 < W|0 < j1 < i0 | |
task->path.erase(task->path.begin()+i0, task->path.end()); | |
task->path.insert(task->path.begin()+j1, rall(ai)); | |
task->path.erase(task->path.begin(), task->path.begin()+rem); | |
} else { // i0 < ilast <= W|0 < j1 | |
task->path.erase(task->path.begin()+i0, task->path.begin()+i0+n); | |
task->path.insert(task->path.begin()+j1, rall(ai)); | |
} | |
} | |
#endif | |
// assert(is_valid_path(task->path, W)); | |
++count; | |
goto found_one; | |
} | |
} | |
} | |
found_one: | |
; | |
// assert(is_valid_path(task->path, W)); | |
} | |
if (count == 0) { | |
goto done; | |
} | |
total += count; | |
} | |
timeout: | |
// total += count; | |
done: | |
if (_verbose) { | |
fprintf(stderr, " tsp_or_opt_n(%g) : z=%d, total=%d\n", qtx, z, total); | |
} | |
//TIME_TO(t0,"<"+to_string(task->mode)+">or-opt#"+to_string(nmax)+", total="+to_string(total)); | |
return total; | |
} | |
void reorder_isles(Task *task) { | |
int mode = task->mode; | |
if (mode == 0) return; | |
if (task->path.size() == 0) return; | |
if (!task->initialized) { | |
fprintf(stderr, "distance_table[][] & path[] in task are not initialized properly\n"); | |
return; | |
} | |
int M = task->isles.size(), W = M+1; | |
if (_verbose) { | |
cerr << "reorder_isles(" << task->desc() << ")" << endl; | |
} | |
assert(task->path.size() == W && task->distance_table.size() == W); | |
#ifdef CHECK_PATH_VALIDITY | |
// assert(is_valid_path(task->path, W)); | |
#endif | |
// assert(task->distance_table.size() == W && task->distance_table[0].size() == W); | |
int dummy_edge = (int)(find(all(task->path), M) - task->path.begin()); | |
//cerr << "OET; " << task->path << M << "," << dummy_edge << endl; | |
//assert(0 <= dummy_edge && dummy_edge < W); | |
// assert(it != task->path.end()); | |
vector<Isle> tmp(all(task->isles)); | |
for (int i=0, j=dummy_edge+1; i<M; ++i,++j) { | |
//assert(0 <= task->path[j%W] && task->path[j%W] < M); | |
//cerr << task->path[j%W] << ", "; | |
task->isles[i] = tmp[task->path[j%W]]; | |
} | |
assert(task->path.size() == W); // |path| mustn't be changed | |
} | |
void reorder_isles4(Task *task) { | |
int mode = task->mode; | |
if (mode == 0) return; | |
int M = task->isles.size(), W = M+1; | |
//assert(is_valid_path4(task->path4, W)); | |
//cerr << "reorder_isles4( " << task->path4 << " ); W=" << W << endl; | |
#ifdef CHECK_PATH_VALIDITY | |
// assert(is_valid_path(task->path, W)); | |
#endif | |
// assert(task->distance_table.size() == W && task->distance_table[0].size() == W); | |
int dummy_edge = -1; | |
rep(i, W) { | |
int p_from = task->path4[i].first; | |
if (M_of_MU(p_from) == M) { dummy_edge = i; break; } | |
} | |
//cerr << "OET; " << task->path << M << "," << dummy_edge << endl; | |
//assert(0 <= dummy_edge && dummy_edge < W); | |
// assert(it != task->path.end()); | |
vector<ii> tmp(all(task->path4)); | |
for (int i=0, j=dummy_edge; i<W; ++i,++j) { | |
task->path4[i] = tmp[j%W]; | |
} | |
} | |
int TSP4(Task *task, double qtx) { | |
assert(task->task_type == TASK_TSP4); | |
int mode = task->mode; | |
if (mode == 0) return 0; | |
int M = task->isles.size(), W = M+1; | |
#ifdef DEBUG | |
if (_verbose) { | |
cerr << "TSP4(" << task->desc() << ", qtx=" << qtx << ")" << endl; | |
} | |
#endif | |
if (!task->initialized) { | |
make_distance_table4(task); | |
tsp4_greedy(task); | |
} | |
if (M <= 3) { | |
return 0; | |
/* | |
task->path4.resize(W); | |
rep(i, W) task->path[i] = i; | |
return 0; | |
*/ | |
} | |
bool immediate_timeout = (M >= 1000); | |
#if 0 | |
int ymod = (M >= 1000) ? 2 : 3; | |
if (M < 100) ymod = 4; | |
if (M < 30) ymod = 1000; | |
#endif | |
int ymod = (M < 100)? 1 : 2; | |
if (M < 30) ymod = 4; | |
// ylim | |
int y = 0, total = 0; | |
for (y=0; ; ++y) { | |
int count = 0; | |
if (y % 2 == 0) { | |
count += tsp4_2_opt(task, qtx); | |
count += tsp4_or_opt_1(task, qtx); | |
count += tsp4_or_opt_n(task, 1, W-2, qtx); | |
count += tsp4_rotate(task, qtx); | |
} else { | |
count += tsp4_2_opt(task, qtx); | |
count += tsp4_or_opt_1(task, qtx); | |
count += tsp4_or_opt_n(task, 2, W-2, qtx); | |
count += tsp4_rotate(task, qtx); | |
} | |
// if ((y % ymod == ymod - 1) && overtime_check(qtx)) { | |
if (_otflag) { | |
goto timeout; | |
} | |
#if 0 | |
{ | |
Distance longest = -9999, supposed; | |
int last_at = -1, longest_at = -1; | |
rep(i, W) { | |
ii edge = task->path4[i]; | |
Distance d; | |
if (M_of_MU(edge.second) == M) { | |
// last | |
last_at = i; | |
int next_vertex = task->path4[(i+1)%W].second; | |
Distance d = task->distance_table4[edge.first][next_vertex]; | |
if (d > longest) { | |
longest = d; | |
longest_at = i; | |
} | |
supposed = d; | |
} else if (M_of_MU(edge.first) == M) { | |
// first | |
continue; | |
} else { | |
Distance d = path4_edge_length(task, i); | |
if (d > longest) { | |
longest = d; | |
longest_at = i; | |
} | |
} | |
} | |
if (longest_at != last_at) { | |
fprintf(stderr, " : LONGEST (%g) edge found at %d (not at %d, %g)\n", longest, longest_at, last_at, supposed); | |
} | |
} | |
#endif | |
if (count == 0) goto done; | |
total += count; | |
} | |
timeout: | |
if (_verbose) { | |
fprintf(stderr, " : overtime = %gmsec\n", _otdelay*1000); | |
} | |
done: | |
if (_verbose) { | |
fprintf(stderr, " => total=%d\n", total); | |
} | |
return total; | |
} | |
int TSP(Task *task, double qtx) { | |
int mode = task->mode; | |
if (mode == 0) return 0; | |
//TIME_FROM(t0); | |
int M = task->isles.size(), W = M+1; | |
#ifdef DEBUG | |
if (_verbose) { | |
cerr << "TSP(" << task->desc() << ", qtx=" << qtx << ")" << endl; | |
} | |
#endif | |
TIME_FROM(t_init); | |
if (!task->initialized) { | |
if (W >= 6000) { | |
task->initialized = true; | |
return 0; | |
} else { | |
make_distance_table(task); | |
if (W < 3) { | |
task->path.resize(W); | |
rep(i, W) task->path[i] = i; | |
} else if (W < 3000 && task->do_tsp_greedy) { | |
tsp_greedy(task); | |
} else { | |
task->path.resize(W); | |
rep(i, W) task->path[i] = i; | |
} | |
if (task->shuffle > 0) { | |
partial_shuffle(task->path, task->shuffle); | |
} | |
} | |
task->initialized = true; | |
if (_verbose) { | |
fprintf(stderr, "[mem] %.2fMB\n", (double)_mem/1048576); | |
} | |
} | |
TIME_TO(t_init,"TSP initialize"); | |
if (task->distance_table.size() != W) { | |
fprintf(stderr, " // invalid distance_table size (%d != %d)\n", (int)task->distance_table.size(), W); | |
return 0; | |
} | |
if (task->path.size() != W) { | |
fprintf(stderr, " // invalid path size (%d != %d)\n", (int)task->path.size(), W); | |
return 0; | |
} | |
_otflag = false; | |
bool immediate_timeout = (M >= 1000); | |
int ymod = (M >= 1000) ? 2 : 3; | |
if (M < 100) ymod = 4; | |
if (M < 30) ymod = 1000; | |
// ylim | |
int total = 0, count = 0, y = 0; | |
for (y=0; ; ++y) { | |
count = 0; | |
TIME_FROM(t_y); | |
if (_verbose) { | |
fprintf(stderr, " y=%d qtx=%g)\n", y, qtx); | |
} | |
if ((y % ymod == ymod - 1) && overtime_check(qtx)) { | |
goto timeout; | |
} | |
count = tsp_2_opt(task, qtx); | |
//if (immediate_timeout && _otflag) goto timeout; | |
if (count == 0) goto done; | |
#define TOO_BIG 2000 | |
// if (M >= 1667) { | |
if (M >= TOO_BIG) { | |
// count += tsp_or_opt_1(task, qtx); /// | |
} else if (M >= 250) { | |
count += tsp_or_opt_1(task, qtx); | |
//if (immediate_timeout && _otflag) goto timeout; | |
} else { | |
count += tsp_or_opt_1(task, qtx); | |
//if (immediate_timeout && _otflag) goto timeout; | |
// count += tsp_or_opt_2(task, qtx); | |
// if (immediate_timeout && _otflag) goto timeout; | |
count += tsp_or_opt_n(task, 2, M-2, qtx); | |
if (immediate_timeout && _otflag) goto timeout; | |
} | |
count = tsp_2_opt(task, qtx); | |
if (M < 250 && !_otflag) | |
count += tsp_or_opt_2(task, qtx); | |
TIME_TO(t_y,"TSP ylim"); | |
if (_verbose) { | |
// double dt = time() - t0; | |
// fprintf(stderr, " %.2fmsec\n", dt); | |
} | |
if (_otflag) goto timeout; | |
if (count == 0) { | |
// fprintf(stderr, " break for count==0\n"); | |
goto done; | |
} | |
total += count; | |
// timeout: | |
// if (y % ymod == ymod - 1) | |
// break; | |
} | |
timeout: | |
// fprintf(stderr, " y.break for timeout\n"); | |
// total += count; | |
if (_verbose) { | |
fprintf(stderr, " : overtime = %gmsec\n", _otdelay*1000); | |
} | |
done: | |
if (_verbose) { | |
fprintf(stderr, " => total=%d\n", total); | |
} | |
//TIME_TO(t0,"<"+to_string(task->mode)+">TSP (M="+to_string(M)+")"); | |
return total; | |
} | |
vector<ii> render_isles(Task *task) { | |
// assert(task->isles.size() == M); | |
//TIME_FROM(t0); | |
vector<ii> out; | |
int M = task->isles.size(); | |
//ii last(-1, -1); | |
int lastr = -1, lastc = -1; | |
rep(i, M) { | |
isle_render(out, task->isles[i], lastr, lastc, | |
i > 0 ? task->isles[i-1] : Isle(-1,-1), | |
i < M-1 ? task->isles[i+1] : Isle(-1,-1) ); | |
} | |
return out; | |
} | |
inline void isle_put4(vector<ii>& out, ii isle, int from, int to) { | |
int r = isle.first, c = isle.second; | |
// fprintf(stderr, "[%d,%d : %d%d%d%d]", r,c, from,(from+2)%4,(to+2)%4,to); | |
#if 1 | |
set<int> tmp; | |
tmp.insert(from); tmp.insert((from+2)%4); tmp.insert((to+2)%4); tmp.insert(to); | |
assert(tmp.size() == 4); | |
#endif | |
out.push_back(ii(r+_dr[from], c+_dc[from])); | |
out.push_back(ii(r+_dr[(from+2)%4], c+_dc[(from+2)%4])); | |
out.push_back(ii(r+_dr[(to+2)%4], c+_dc[(to+2)%4])); | |
out.push_back(ii(r+_dr[to], c+_dc[to])); | |
} | |
vector<ii> render_isles4(Task *task) { | |
// cerr << "render_isles4( " << task->path4 << " )" << endl; | |
//TIME_FROM(t0); | |
vector<ii> out; | |
int M = task->isles.size(), W = M+1; | |
fprintf(stderr, "render_isles4(). M=%d, W=%d, |path4|=%d\n", M, W, (int)task->path4.size()); | |
// assert(is_valid_path4(task->path4, W)); | |
assert(task->path4.size() == W); | |
int last; | |
rep(i, M+1) { | |
int p1 = task->path4[i].first, p2 = task->path4[i].second; | |
// isle_render4(out, p1, p2); | |
if (M_of_MU(p1) == M) { | |
// first | |
last = p2; continue; | |
} | |
else if (M_of_MU(p2) == M) { | |
// [draw] last .. p1 | |
assert(M_of_MU(last) == M_of_MU(p1)); | |
isle_put4(out, task->isles[M_of_MU(last)], U_of_MU(last), U_of_MU(p1)); | |
break; | |
} | |
else { | |
// [draw] last .. p1 | |
assert(M_of_MU(last) == M_of_MU(p1)); | |
isle_put4(out, task->isles[M_of_MU(last)], U_of_MU(last), U_of_MU(p1)); | |
last = p2; continue; | |
} | |
} | |
// fprintf(stderr, "\n"); | |
return out; | |
} | |
class CrossStitch { | |
public: | |
CrossStitch() {} | |
~CrossStitch() {} | |
private: | |
int S; | |
private: | |
int parse_window1(vector<Isle>& isles, vector<vector<int> >& pa, int color) { | |
#if 0 | |
vector<Isle> isles; | |
rep(r, S) rep(c, S) { | |
if (pa[r][c] != color) continue; | |
isles.push_back(Isle(r, c)); | |
} | |
#else | |
map<int, vector<int> > tmp; | |
rep(r, S) rep(c, S) { | |
if (pa[r][c] != color) continue; | |
tmp[r].push_back(c); | |
// isles.push_back(Isle(r, c)); | |
} | |
// vector<Isle> isles; | |
bool reversed = false; | |
tr(rt, tmp) { | |
int r = rt->first; | |
// int cn = rt->second.size(); | |
if (reversed) { | |
rtr(ct, rt->second) { | |
int c = *ct; | |
isles.push_back(Isle(r, c)); | |
} | |
} else { | |
tr(ct, rt->second) { | |
int c = *ct; | |
isles.push_back(Isle(r, c)); | |
} | |
} | |
reversed = !reversed; | |
} | |
#endif | |
return isles.size(); | |
} | |
void check(vector<ii>& out, vector<vector<int> >& pa, int color) { | |
TIME_FROM(t_check); | |
int M = out.size(); | |
assert(M > 0 && M % 2 == 0); | |
vector<vector<int> > z(S, vector<int>(S, 0)); | |
int lastr = out[0].first, lastc = out[0].second; | |
for (int i=1; i<M; ++i) { | |
int r = out[i].first, c = out[i].second; | |
if (i % 2) { | |
assert(abs(r - lastr) == 1 && abs(c - lastc) == 1); | |
int pr = min(r, lastr), pc = min(c, lastc); | |
++z[pr][pc]; | |
} | |
lastr = r; lastc = c; | |
} | |
rep(r,S) rep(c,S) { | |
int cnt = z[r][c]; | |
assert( (cnt == 0 && pa[r][c] != color) | |
|| (cnt == 2 && pa[r][c] == color) ); | |
} | |
TIME_TO(t_check,"check"); | |
} | |
double score(double L, double total_usage) { | |
double W = total_usage - L; | |
return max(0.0, pow((5.0 - W/L)/5.0, 3)); | |
} | |
double count_used(vector<ii>& out) { | |
double d = 0.0; | |
int last_r, last_c; | |
for (int j=0,z=out.size(); j<z; ++j) { | |
int r = out[j].first, c = out[j].second; | |
if (j > 0) { | |
d += hypot(r - last_r, c - last_c); | |
} | |
last_r = r; last_c = c; | |
} | |
return d; | |
} | |
void append_to_result(vector<string>& ret, char color, vector<ii>& solution) { | |
//TIME_FROM(t0); | |
ret.push_back(string(1, color)); | |
for (int j=0,z=solution.size(); j<z; ++j) { | |
int r = solution[j].first, c = solution[j].second; | |
ret.push_back(to_string(r) + " " + to_string(c)); | |
} | |
//TIME_TO(t0,"append_to_result " + to_string(color-'a')); | |
} | |
double _start_time; | |
double lapse() { | |
return time() - _start_time; | |
} | |
public: | |
vector<vector<int> > pa; | |
vector<string> embroider(vector<string> pattern) { | |
srand(1337); | |
_start_time = time(); | |
//TIME_FROM(t_embroider); | |
if (_verbose) { | |
fprintf(stderr, "time limit = %gsec.\n", _time_limit); | |
} | |
vector<string> result; | |
S = pattern.size(); // this->S | |
pa.assign(S, vector<int>(S, 0)); | |
stringstream ss; | |
ss << "[S=" << S << "]"; | |
double L = 0.0, total = 0.0; | |
vector<int> color_count(20, 0); | |
rep(r,S) rep(c,S) { | |
int color = pattern[r][c]; | |
if (color == '.') continue; | |
int color_ix = color - 'a'; | |
pa[r][c] = color; | |
++color_count[color_ix]; | |
} | |
int num_of_colors = 0; | |
rep(i, 20) { | |
if (color_count[i] == 0) break; | |
++num_of_colors; | |
} | |
color_count.resize(num_of_colors); | |
vector<int> quota_score(num_of_colors, 0); | |
int total_pixels = 0, total_score = 0; | |
rep(color_ix, num_of_colors) { | |
int pixels = color_count[color_ix]; | |
total_pixels += pixels; | |
int score = square(pixels); | |
// int score = pow(pixels, 2.5); | |
quota_score[color_ix] = score; | |
total_score += score; | |
} | |
vector<double> quota(num_of_colors, 0.0); | |
rep(color_ix, num_of_colors) { | |
quota[color_ix] = (double)quota_score[color_ix] / total_score; | |
if (_verbose) { | |
fprintf(stderr, " %c) %d/%d, quota=%g\n", | |
'a'+color_ix, // num_of_colors, | |
color_count[color_ix], total_pixels, quota[color_ix]); | |
} | |
} | |
//TIME_TO(t0,"preparation"); | |
priority_queue<pair<double, int> > pq; | |
rep(color_ix, num_of_colors) { | |
pq.push(make_pair(quota[color_ix], color_ix)); | |
} | |
vector<vector<ii> > solutions(20); | |
double quota_remains = 1.0; | |
// rep(color_ix, num_of_colors) { | |
while (!pq.empty()) { | |
double _quota = pq.top().first, color_ix = pq.top().second; pq.pop(); | |
//TIME_FROM(t1); | |
int color = 'a' + color_ix; | |
double color_start = time(); // color_start; | |
double time_remains = _time_limit - (color_start - _start_time); // lapse(); | |
double qtime = (time_remains / quota_remains) * _quota; | |
qtime = min(qtime, 1.0 / num_of_colors); | |
quota_remains -= _quota; | |
// double qtime = quota[color_ix] * (_time_limit * 0.98); | |
#ifdef DEBUG | |
if (_verbose) { | |
fprintf(stderr, "\n[[color=%c]] M=%d; lapse=%g, qtime=%g, otc=%d\n", color, color_count[color_ix], (color_start - _start_time), qtime, _otc); // 20 times at maximum | |
} | |
#endif | |
assert(/* 0 <= qtime && */ qtime < _time_limit); | |
int pixels = color_count[color_ix]; | |
assert(pixels > 0); | |
double local_L = sqrt(2.0) * 2 * pixels; | |
if (_verbose) { | |
// fprintf(stderr, " // quota[%c, %dpixels]: %g x %g = %g sec\n", color, pixels, quota[color_ix], _time_limit, qtime); | |
} | |
//TIME_FROM(t5); | |
vector<Task*> tasks; | |
int mode = 1; | |
int M = pixels; | |
if (M < 250) { | |
char *caption = NULL; | |
asprintf(&caption, "%c_%d_m%d_TSP4", color, M, mode); | |
Task *task = new Task(S, color, TASK_TSP4, caption, mode, true, true, 0.2); | |
parse_window1(task->isles, pa, color); | |
_mem += (sizeof(Isle) + sizeof(Distance)) * M; | |
tasks.push_back(task); | |
free(caption); | |
} | |
{ | |
char *caption = NULL; | |
asprintf(&caption, "%c_%d_m%d_tG+", color, M, mode); | |
Task *task = new Task(S, color, TASK_WINDOW, caption, mode, true, true, 0.0); | |
parse_window1(task->isles, pa, color); | |
M = task->isles.size(); | |
_mem += (sizeof(Isle) + sizeof(Distance)) * M; | |
tasks.push_back(task); | |
free(caption); | |
} | |
//#define DO_OTHER_TASKS 1 | |
#ifdef DO_OTHER_TASKS | |
if (M < 300) { | |
char *caption = NULL; | |
asprintf(&caption, "%c_%d_m%d_tG", color, M, mode); | |
Task *task = new Task(S, color, TASK_WINDOW, caption, mode, true, false, 0.0); | |
parse_window1(task->isles, pa, color); | |
_mem += (sizeof(Isle) + sizeof(Distance)) * M; | |
tasks.push_back(task); | |
free(caption); | |
} | |
/* | |
if (M < 200) { | |
char *caption = NULL; | |
asprintf(&caption, "%c_%d_m%d_tG+25", color, M, mode); | |
Task *task = new Task(S, color, TASK_WINDOW, caption, mode, true, true, 0.25); | |
parse_window1(task->isles, pa, color); | |
_mem += (sizeof(Isle) + sizeof(Distance)) * M; | |
tasks.push_back(task); | |
free(caption); | |
} | |
if (M < 100) { | |
char *caption = NULL; | |
asprintf(&caption, "%c_%d_m%d_tG+20", color, M, mode); | |
Task *task = new Task(S, color, TASK_WINDOW, caption, mode, true, true, 0.2); | |
parse_window1(task->isles, pa, color); | |
_mem += (sizeof(Isle) + sizeof(Distance)) * M; | |
tasks.push_back(task); | |
free(caption); | |
} | |
*/ | |
if (M < 300) { | |
char *caption = NULL; | |
asprintf(&caption, "%c_%d_m%d_R100", color, M, mode); | |
Task *task = new Task(S, color, TASK_WINDOW, caption, mode, false, true, 1.0); | |
parse_window1(task->isles, pa, color); | |
_mem += (sizeof(Isle) + sizeof(Distance)) * M; | |
tasks.push_back(task); | |
free(caption); | |
} | |
#endif | |
/* | |
if (M < 75) { | |
char *caption = NULL; | |
asprintf(&caption, "%c_m%d_t_s3", color, mode); | |
Task *task = new Task(S, color, TASK_WINDOW, caption, mode, true, 0.5); | |
parse_window1(task->isles, pa, color); | |
_mem += (sizeof(Isle) + sizeof(Distance)) * M; | |
tasks.push_back(task); | |
free(caption); | |
} | |
*/ | |
if (_verbose) { | |
fprintf(stderr, " // %d task(s) :", (int)tasks.size()); | |
rep(i, tasks.size()) { | |
fprintf(stderr, " %s", tasks[i]->caption.c_str()); | |
} | |
fprintf(stderr, "\n"); | |
} | |
//TIME_TO(t5,"task_preparation"); | |
double best_score = 0.0; | |
double best_usage = 0.0; | |
vector<ii> best_solution; | |
string best_at; | |
// int iter = 1; | |
// for (int iter=1; iter<=1; ++iter) { | |
{ | |
int num_of_remaining_tasks = 0; | |
rep(i, tasks.size()) if (!tasks[i]->converged) ++num_of_remaining_tasks; | |
if (_verbose) { | |
// fprintf(stderr, "[iter]%dth iteration; %d tasks\n", iter, num_of_remaining_tasks); | |
fprintf(stderr, "%d tasks\n", num_of_remaining_tasks); | |
} | |
// if (overtime_check(qtx)) goto timeout; | |
int total = 0; | |
// double qtime_per_task = qtime ;/// tasks.size(); | |
double qtime_per_task = qtime / tasks.size(); | |
rep(i, tasks.size()) { | |
Task *task = tasks[i]; | |
if (task->converged) continue; | |
double task_i_start = time(); | |
if (i == 0) { | |
if (_verbose) { | |
double dt = task_i_start - color_start; | |
fprintf(stderr, " // %gsec before first task\n", dt); | |
} | |
} | |
double qtx = task_i_start + qtime_per_task; // 20 times at maximum | |
if (_verbose) { | |
fprintf(stderr, ":: now=%g qtx=%g \n", time(), qtx); | |
} | |
if (i > 0 && task->size() >= 400) { | |
if (overtime_check(qtx)) goto timeout; | |
} | |
if (task->mode >= 1) { | |
int count = 0; | |
if (task->task_type == TASK_TSP4) { | |
count = TSP4(task, qtx); | |
reorder_isles4(task); | |
} else { | |
count = TSP(task, qtx); | |
reorder_isles(task); | |
} | |
if (count == 0) { | |
task->converged = true; | |
} | |
total += count; | |
} else { | |
task->converged = true; | |
} | |
//TIME_FROM(t7); | |
vector<ii> out; | |
if (task->task_type == TASK_TSP4) { | |
out = render_isles4(task); | |
assert(out.size() == task->size()*4); | |
} else { | |
out = render_isles(task); | |
} | |
if (_check) check(out, pa, color); | |
double u = count_used(out); | |
double sc = score(local_L, u); | |
if (_verbose) { | |
double dt = time() - task_i_start; | |
fprintf(stderr, " // %s: score = %g (L=%g W=%g), dt=%g / %g\n", task->caption.c_str(), sc, local_L, u-local_L, dt, qtime_per_task); | |
fprintf(stderr, ":: now=%g qtx=%g \n", time(), qtx); | |
} | |
if (sc > best_score) { | |
best_solution.assign(all(out)); | |
best_score = sc; | |
best_usage = u; | |
best_at = task->caption; | |
} | |
#ifdef DEBUG | |
if (_export) { | |
char *filename = NULL; | |
// asprintf(&filename, "debug/%s_i%d.out", task->caption.c_str(), iter); | |
asprintf(&filename, "debug/%s.out", task->caption.c_str()); | |
export_solution(filename, S, task->isles, out); | |
free(filename); | |
} | |
#endif | |
} | |
if (total == 0) goto done; | |
} | |
timeout: | |
; | |
done: | |
; | |
//TIME_FROM(t6); | |
rep(i, tasks.size()) { | |
delete tasks[i]; // 4msecぐらいかかってる | |
} | |
tasks.clear(); | |
if (_verbose) { | |
cerr << " // best at: " << best_at << endl; | |
} | |
ss << "[" << best_at << "]"; | |
solutions[color_ix].assign(all(best_solution)); | |
L += local_L; | |
total += best_usage; | |
//TIME_TO(t6,"task_postprocess"); | |
//TIME_TO(t1,"color "+to_string(color_ix)); | |
} | |
rep(color_ix, num_of_colors) { | |
append_to_result(result, 'a'+color_ix, solutions[color_ix]); | |
} | |
double s = score(L, total); | |
fprintf(stderr, "Score = %.17f ; lapse = %g ; otc = %d ; %s\n", s, lapse(), _otc, ss.str().c_str()); // 1 | |
return result; | |
} | |
}; | |
// BEGIN CUT HERE | |
int main(int argc, char *argv[]) { | |
int S = -1; | |
vector<string> pattern; | |
// input | |
for (int i=1; i<argc; ++i) { | |
if (argv[i][0] == '-') { | |
switch (argv[i][1]) { | |
case 'v': | |
_verbose = true; break; | |
case 's': case 'x': | |
_export = true; break; | |
case 'c': | |
_check = _verbose = true; break; | |
case 't': | |
if (i+1 < argc) { | |
_time_limit = (double)atoi(argv[i+1]); | |
++i; | |
} | |
break; | |
default: | |
break; | |
} | |
} else { | |
//TIME_FROM(t1); | |
ifstream f; | |
f.open(argv[i]); if (!f) continue; | |
f >> S; | |
pattern.resize(S); | |
rep(i, S) f >> pattern[i]; | |
f.close(); | |
//TIME_TO(t1, "INPUT"); | |
} | |
} | |
if (S == -1) { | |
//TIME_FROM(t1); | |
cin >> S; | |
pattern.resize(S); | |
rep(i, S) cin >> pattern[i]; | |
//TIME_TO(t1, "INPUT"); | |
} | |
// solve | |
CrossStitch app; | |
vector<string> ret = app.embroider(pattern); | |
// output | |
//TIME_FROM(t2); | |
cout << ret.size() << endl; | |
rep(i, ret.size()) | |
cout << ret[i] << endl; | |
cout.flush(); | |
//TIME_TO(t2,"OUTPUT"); | |
if (_verbose) { | |
fprintf(stderr, "memory usage: %.2fMB, clock() was called %d times (otc=%d)\n", (double)_mem / 1048576, _clock_called, _otc); | |
} | |
return 0; | |
} | |
// END CUT HERE |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment