/* upsolve after reading analysis */
#include "scales.h"
#include <string.h>
#define N 6
#define M 720
#define N_ 1093
#define K 6
int p3[] = { 1, 3, 9, 27, 81, 243, 729 };
int next_permutation(int *pp) {
int i, j, tmp;
i = N - 2;
while (i >= 0 && pp[i] > pp[i + 1])
i--;
if (i < 0)
return 0;
j = N - 1;
while (j > 0 && pp[i] > pp[j])
j--;
tmp = pp[i], pp[i] = pp[j], pp[j] = tmp;
for (i++, j = N - 1; i < j; i++, j--)
tmp = pp[i], pp[i] = pp[j], pp[j] = tmp;
return 1;
}
int ppp[M][N]; char type[K + 1][M];
int mode_[N_], aa[N_], bb[N_], cc[N_], dd[N_];
int query(int *pp, int mode, int a, int b, int c, int d) {
if (mode == 3) {
if (pp[d] > pp[a] && pp[d] > pp[b] && pp[d] > pp[c])
mode = 0;
else {
if (pp[a] > pp[d] && (pp[b] < pp[d] || pp[b] > pp[a]) && (pp[c] < pp[d] || pp[c] > pp[a]))
return 1;
if (pp[b] > pp[d] && (pp[a] < pp[d] || pp[a] > pp[b]) && (pp[c] < pp[d] || pp[c] > pp[b]))
return 2;
return 3;
}
}
if (mode == 0) {
if (pp[a] < pp[b] && pp[a] < pp[c])
return 1;
if (pp[b] < pp[a] && pp[b] < pp[c])
return 2;
return 3;
}
if (mode == 1) {
if (pp[a] > pp[b] && pp[a] > pp[c])
return 1;
if (pp[b] > pp[a] && pp[b] > pp[c])
return 2;
return 3;
}
if (mode == 2) {
if ((pp[a] > pp[b]) != (pp[a] > pp[c]))
return 1;
if ((pp[b] > pp[a]) != (pp[b] > pp[c]))
return 2;
return 3;
}
return -1;
}
int dfs(int u, int k) {
static int cnt[4];
int h, h_;
h_ = -1;
for (h = 0; h < M; h++)
if (type[k][h]) {
if (h_ == -1)
h_ = h;
else {
h_ = -2;
break;
}
}
if (h_ == -1)
return 1;
if (h_ != -2) {
mode_[u] = -h_ - 1;
return 1;
}
for (mode_[u] = 0; mode_[u] < 4; mode_[u]++)
for (aa[u] = 0; aa[u] < N; aa[u]++)
for (bb[u] = aa[u] + 1; bb[u] < N; bb[u]++)
for (cc[u] = bb[u] + 1; cc[u] < N; cc[u]++)
for (dd[u] = 0; dd[u] < (mode_[u] == 3 ? N : 1); dd[u]++) {
int t, ok;
if (mode_[u] == 3 && (dd[u] == aa[u] || dd[u] == bb[u] || dd[u] == cc[u]))
continue;
cnt[1] = cnt[2] = cnt[3] = 0;
for (h = 0; h < M; h++)
if (type[k][h])
cnt[type[k][h] = query(ppp[h], mode_[u], aa[u], bb[u], cc[u], dd[u])]++;
if (cnt[1] > p3[K - 1 - k] || cnt[2] > p3[K - 1 - k] || cnt[3] > p3[K - 1 - k])
continue;
ok = 1;
for (t = 1; t <= 3; t++) {
for (h = 0; h < M; h++)
type[k + 1][h] = type[k][h] == t;
if (!dfs(u * 3 + t, k + 1)) {
ok = 0;
break;
}
}
if (ok)
return 1;
}
return 0;
}
void init(int T) {
static int pp[N];
int i, m;
for (i = 0; i < N; i++)
pp[i] = i;
m = 0;
do {
memcpy(ppp[m++], pp, N * sizeof *pp);
} while (next_permutation(pp));
memset(type[0], 1, M * sizeof *type[0]);
dfs(0, 0);
}
void orderCoins() {
static int ans[N];
int h, i, u;
u = 0;
while (mode_[u] >= 0) {
int x;
if (mode_[u] == 0)
x = getLightest(aa[u] + 1, bb[u] + 1, cc[u] + 1) - 1;
else if (mode_[u] == 1)
x = getHeaviest(aa[u] + 1, bb[u] + 1, cc[u] + 1) - 1;
else if (mode_[u] == 2)
x = getMedian(aa[u] + 1, bb[u] + 1, cc[u] + 1) - 1;
else
x = getNextLightest(aa[u] + 1, bb[u] + 1, cc[u] + 1, dd[u] + 1) - 1;
if (x == aa[u])
u = u * 3 + 1;
else if (x == bb[u])
u = u * 3 + 2;
else
u = u * 3 + 3;
}
h = -1 - mode_[u];
for (i = 0; i < 6; i++)
ans[ppp[h][i]] = i + 1;
answer(ans);
}
