#include "scales.h"
#include <cassert>
#include <vector>
#include <array>
#include <algorithm>
#include <numeric>
#include <cstring>
template<typename T> bool ckmax(T& a, const T& b) {return b>a?a=b,1:0;}
template<typename T> bool ckmin(T& a, const T& b) {return b<a?a=b,1:0;}
const int MN = 6;
const int MP = 6*5*4*3*2*1;
using arr = std::array<int, MN>;
arr p[MP];
struct move
{
public:
int type, v[3], D;
int qry()
{
if(type==0)
return getLightest(v[0], v[1], v[2]);
if(type==1)
return getMedian(v[0], v[1], v[2]);
if(type==2)
return getHeaviest(v[0], v[1], v[2]);
if(type==3)
return getNextLightest(v[0], v[1], v[2], D);
assert(0);
return -1;
}
};
std::vector<move> moves;
void init(int T) {
arr a;
std::iota(a.begin(), a.end(), 1);
int ctr=0;
do
{
p[ctr++]=a;
} while (std::next_permutation(a.begin(), a.end()));
for(int i=1;i<=MN;++i)
for(int j=i+1;j<=MN;++j)
for(int k=j+1;k<=MN;++k)
{
moves.push_back({0, i, j, k, -1});
moves.push_back({1, i, j, k, -1});
moves.push_back({2, i, j, k, -1});
for(int l=1;l<=MN;++l)
if(l != i && l != j && l != k)
moves.push_back({3, i, j, k, l});
}
}
int get(const arr& a, const move& m)
{
auto cmp=[&](int u, int v) {return a[u-1]<a[v-1];};
int v[3] = {m.v[0], m.v[1], m.v[2]};
std::sort(v, v+3, cmp);
if(m.type == 3)
{
int x=m.D;
for(int i=1;i<3;++i)
if(cmp(v[i-1], x) && cmp(x, v[i]))
return v[i];
return v[0];
}
else
{
return v[m.type];
/* //-- retrieve index
for(int i=0;i<3;++i)
if(m.v[i]==v[m.type])
return i;
*/
}
assert(0);
return -1;
}
void orderCoins() {
/* ... */
int W[] = {1, 2, 3, 4, 5, 6};
std::vector<arr> ok(p, p+MP), ok2;
while(ok.size() > 1)
{
//printf("ok sz: %lu\n", ok.size());
int id=-1, best=MP+1;
for(int i=0;i<moves.size();++i)
{
int v[6]; memset(v, 0, sizeof v);
for(const auto& x:ok)
v[get(x, moves[i])-1]++;
if(ckmin(best, *std::max_element(v, v+6)))
id=i;
}
int q = moves[id].qry();
//printf("Type %d: %d %d %d [%d]: %d\n", moves[id].type, moves[id].v[0], moves[id].v[1], moves[id].v[2] ,moves[id].D, q);
for(const auto& x:ok)
if(get(x, moves[id])==q)
ok2.push_back(x);
ok2.swap(ok);
ok2.clear();
}
for(int i=0;i<6;++i)
W[ok[0][i]-1]=i+1;
answer(W);
}
