Skip to content

Instantly share code, notes, and snippets.

@naoyat

naoyat/mm93.cc Secret

Created March 17, 2017 04:15
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save naoyat/e6336534425bf787731722a66af2d8b8 to your computer and use it in GitHub Desktop.
Save naoyat/e6336534425bf787731722a66af2d8b8 to your computer and use it in GitHub Desktop.
Download ZIP
MM93:最終submitコード
Raw
mm93.cc
#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