// Oh damn! Suddenly you're free to fly...
#include<bits/stdc++.h>
#include "scales.h"
#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e5 + 10, mod = 1e9 + 7, inf = 1e9 + 10;
int perms[720][6];
int arr[6];
struct node{
vector<int> posib;
int A, B, C, D, Task;
node *v[3];
};
node* root;
int fnd(int id, int x){
assert(id < 720);
for(int i = 0; i < 6; i++)
if(perms[id][i] == x)
return i;
assert(0);
}
function<int(int,int,int,int,int)> calc[4] = {
[](int id, int a, int b, int c, int d = -1){
a = fnd(id, a), b = fnd(id, b), c = fnd(id, c);
int mx = max({a, b, c});
if(mx == a)
return 0;
if(mx == b)
return 1;
if(mx == c)
return 2;
assert(0);
},
[](int id, int a, int b, int c, int d = -1){
a = fnd(id, a), b = fnd(id, b), c = fnd(id, c);
int A = a, B = b, C = c;
if(A > B)
swap(A, B);
if(A > C)
swap(A, C);
if(B > C)
swap(B, C);
if(B == a)
return 0;
if(B == b)
return 1;
if(B == c)
return 2;
assert(0);
},
[](int id, int a, int b, int c, int d = -1){
a = fnd(id, a), b = fnd(id, b), c = fnd(id, c);
int mn = min({a, b, c});
if(mn == a)
return 0;
if(mn == b)
return 1;
if(mn == c)
return 2;
assert(0);
},
[](int id, int a, int b, int c, int d){
a = fnd(id, a), b = fnd(id, b), c = fnd(id, c), d = fnd(id, d);
int A = a, B = b, C = c;
if(A > B)
swap(A, B);
if(A > C)
swap(A, C);
if(B > C)
swap(B, C);
int ret = -1;
if(d < A)
ret = A;
else if(d < B)
ret = B;
else if(d < C)
ret = C;
else
ret = A;
if(a == ret)
return 0;
if(b == ret)
return 1;
if(c == ret)
return 2;
assert(0);
}
};
int mx_task(int task, vector<int> &v, int a, int b, int c, int d = -1){
int sc[3] = {0, 0, 0};
for(int id : v)
sc[calc[task](id, a, b, c, d)]++;
return max({sc[0], sc[1], sc[2]});
}
int dif_task(int task, vector<int> &v, int a, int b, int c, int d = -1){
int sc[3] = {0, 0, 0};
for(int id : v)
sc[calc[task](id, a, b, c, d)]++;
return max({sc[0], sc[1], sc[2]}) - min({sc[0], sc[1], sc[2]});
}
void fil_task(int task, node *u, int a, int b, int c, int d = -1){
u->A = a, u->B = b, u->C = c, u->D = d, u->Task = task;
u->v[0] = new node(), u->v[1] = new node(), u->v[2] = new node();
for(int id : u->posib)
u->v[calc[task](id, a, b, c, d)]->posib.PB(id);
}
int TW[10];
bool dfs(node* u, int h = 0){
assert(h <= 6);
if(h == 6)
assert(sz(u->posib) <= 1);
if(sz(u->posib) <= 1)
return 1;
for(int i = 0; i < 6; i++)
for(int j = i+1; j < 6; j++)
for(int k = j+1; k < 6; k++){
fil_task(0, u, i, j, k);
if(mx_task(0, u->posib, i, j, k) <= TW[6-h-1] && dfs(u->v[0], h+1) && dfs(u->v[1], h+1) && dfs(u->v[2], h+1))
return 1;
fil_task(1, u, i, j, k);
if(mx_task(1, u->posib, i, j, k) <= TW[6-h-1] && dfs(u->v[0], h+1) && dfs(u->v[1], h+1) && dfs(u->v[2], h+1))
return 1;
fil_task(2, u, i, j, k);
if(mx_task(2, u->posib, i, j, k) <= TW[6-h-1] && dfs(u->v[0], h+1) && dfs(u->v[1], h+1) && dfs(u->v[2], h+1))
return 1;
for(int w = 0; w < 6; w++){
if(w != i && w != j && w != k){
fil_task(3, u, i, j, k, w);
if(mx_task(3, u->posib, i, j, k, w) <= TW[6-h-1] && dfs(u->v[0], h+1) && dfs(u->v[1], h+1) && dfs(u->v[2], h+1))
return 1;
}
}
}
return 0;
/* int bst = inf, cntbst = 0;
auto better = [&](int x){
if(x < bst)
bst = x, cntbst = 0;
cntbst+= x == bst;
};
for(int i = 0; i < 6; i++)
for(int j = i+1; j < 6; j++)
for(int k = j+1; k < 6; k++){
better(dif_task(0, u->posib, i, j, k));
better(dif_task(1, u->posib, i, j, k));
better(dif_task(2, u->posib, i, j, k));
for(int w = 0; w < 6; w++){
if(w != i && w != j && w != k){
better(dif_task(3, u->posib, i, j, k, w));
}
}
}
cntbst = rand() % cntbst;
for(int i = 0; i < 6; i++)
for(int j = i+1; j < 6; j++)
for(int k = j+1; k < 6; k++){
if(bst == dif_task(0, u->posib, i, j, k) && cntbst-- == 0){
fil_task(0, u, i, j, k);
goto Hell;
}
if(bst == dif_task(1, u->posib, i, j, k) && cntbst-- == 0){
fil_task(1, u, i, j, k);
goto Hell;
}
if(bst == dif_task(2, u->posib, i, j, k) && cntbst-- == 0){
fil_task(2, u, i, j, k);
goto Hell;
}
for(int w = 0; w < 6; w++){
if(w != i && w != j && w != k){
if(bst == dif_task(3, u->posib, i, j, k, w) && cntbst-- == 0){
fil_task(3, u, i, j, k, w);
goto Hell;
}
}
}
}
Hell:;
cerr << sz(u->posib) << ": " << sz(u->v[0]->posib) << " " << sz(u->v[1]->posib) << " " << sz(u->v[2]->posib) << endl;
dfs(u->v[0], h+1), dfs(u->v[1], h+1), dfs(u->v[2], h+1);
return;*/
}
void init(int T){
TW[0] = 1;
for(int i = 1; i < 10; i++)
TW[i] = 3 * TW[i-1];
srand(time(0));
iota(arr, arr + 6, 0);
int C = 0;
do{
for(int i = 0; i < 6; i++)
perms[C][i] = arr[i];
C++;
}while(next_permutation(arr, arr + 6));
root = new node();
for(int i = 0; i < 720; i++){
root->posib.PB(i);
}
dfs(root);
}
void orderCoins(){
node *now = root;
int asked = 0;
while(sz(now->posib) > 1){
int id = -1;
if(now->Task == 0)
id = getHeaviest(now->A + 1, now->B + 1, now->C + 1);
else if(now->Task == 1)
id = getMedian(now->A + 1, now->B + 1, now->C + 1);
else if(now->Task == 2)
id = getLightest(now->A + 1, now->B + 1, now->C + 1);
else if(now->Task == 3)
id = getNextLightest(now->A + 1, now->B + 1, now->C + 1, now->D + 1);
if(id == now->A + 1)
id = 0;
else if(id == now->B + 1)
id = 1;
else
id = 2;
now = now->v[id];
asked++;
}
int ans[6];
for(int i = 0; i < 6; i++){
ans[i] = perms[now->posib[0]][i] + 1;
}
answer(ans);
// answer
// getHeaviest
// getMedian
// getLightest
// getNextLightest
}
