#include "fun.h"
#include <cassert>
#include <vector>
using namespace std;
const int N = 100000;
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
int dd[N];
void sort(int *ii, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;
while (j < k)
if (dd[ii[j]] == dd[i_])
j++;
else if (dd[ii[j]] < dd[i_]) {
tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
i++, j++;
} else {
k--;
tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
}
sort(ii, l, i);
l = k;
}
}
vector<int> createFunTour(int n, int q) {
static int type[N], qu[3][N], cnt[3];
vector<int> pp = vector<int>(n);
int n_, h, h_, i, i_, u, a, b, c, sz_;
q = -1;
sz_ = n + 1, u = -1;
for (i = 0; i < n; i++) {
int sz = attractionsBehind(0, i);
if ((n - sz) * 2 <= n && sz_ > sz)
sz_ = sz, u = i;
}
a = -1, b = -1, c = -1;
for (i = 0; i < n; i++)
if (i != u) {
dd[i] = hoursRequired(u, i);
if (dd[i] == 1) {
if (a == -1)
a = i;
else if (b == -1)
b = i;
else
c = i;
}
}
for (i = 0; i < n; i++)
if (i != u) {
if (hoursRequired(a, i) == dd[i] - 1)
type[i] = 0, qu[0][cnt[0]++] = i;
else if (hoursRequired(b, i) == dd[i] - 1)
type[i] = 1, qu[1][cnt[1]++] = i;
else
type[i] = 2, qu[2][cnt[2]++] = i;
}
for (h = 0; h < 3; h++)
sort(qu[h], 0, cnt[h]);
i_ = -1;
for (h = 0; h < 3; h++)
if (cnt[h]) {
i = qu[h][cnt[h] - 1];
if (i_ == -1 || dd[i_] < dd[i])
i_ = i;
}
h_ = -1;
for (h = 0; h < 3; h++)
if (cnt[h] >= cnt[(h + 1) % 3] + cnt[(h + 2) % 3]) {
h_ = h;
break;
}
n_ = 0;
if (h_ == -1) {
i = i_;
while (1) {
pp[n_++] = i, cnt[h_ = type[i]]--;
if (n == n_)
break;
i_ = -1;
for (h = 0; h < 3; h++)
if (h != h_ && cnt[h]) {
int i1 = qu[h][cnt[h] - 1];
if (i_ == -1 || dd[i_] < dd[i1])
i_ = i1;
}
for (h = 0; h < 3; h++)
if (h != type[i_] && cnt[h] == cnt[(h + 1) % 3] + cnt[(h + 2) % 3]) {
if (dd[i] < dd[i_])
pp[n_++] = i_, cnt[type[i_]]--;
h_ = h;
goto out;
}
i = i_;
}
out:;
}
while (cnt[h_]) {
int h1, h2;
pp[n_++] = cnt[h_] == 0 ? u : qu[h_][--cnt[h_]];
if (n - n_ == 1)
break;
h1 = (h_ + 1) % 3, h2 = (h_ + 2) % 3;
pp[n_++] = !cnt[h2] || cnt[h1] && dd[qu[h1][cnt[h1] - 1]] > dd[qu[h2][cnt[h2] - 1]] ? qu[h1][--cnt[h1]] : qu[h2][--cnt[h2]];
}
pp[n_++] = u;
return pp;
}
