#include "scales.h"
#include <bits/stdc++.h>
#define all(a) a.begin(), a.end()
using namespace std;
typedef pair<int, int> pii;
typedef pair<int, vector<int> > op_info;
const int num_coins = 6;
const int INF = 1e9;
vector<vector<int> > threes, fours, perms;
map<vector<int>, int> perm_to_idx;
map<vector<int>, op_info> best_op;
void get_guys(int curr, int lft, vector<int> me, vector<vector<int> > &add) {
if (lft == 0) {
add.push_back(me);
return;
}
if (curr == num_coins + 1)
return;
get_guys(curr + 1, lft, me ,add);
me.push_back(curr);
get_guys(curr + 1, lft - 1, me, add);
}
int get_outcome(int op_type, vector<int> &op, vector<int> &me) {
vector<int> ord;
int four_weight = -1, id;
for (int i = 0; i < 6; i++)
{
if (me[i] == op[2])
ord.push_back(op[2]);
else if (me[i] == op[0])
ord.push_back(op[0]);
else if (me[i] == op[1])
ord.push_back(op[1]);
else if (op_type == 4 and op[3] == me[i])
{
four_weight = i;
if (ord.size() == 3)
return ord[0];
id = ord.size();
}
}
if (op_type == 1)
return ord.back();
else if (op_type == 2)
return ord[0];
else if (op_type == 3)
return ord[1];
else
return ord[id];
}
vector<vector<int> > get_split(int op_type, vector<int> &poss, vector<int> &op) {
vector<vector<int> > out(3);
for (int me : poss) {
int outcome = get_outcome(op_type, op, perms[me]);
if (outcome == op[0])
out[0].push_back(me);
else if (outcome == op[1])
out[1].push_back(me);
else
out[2].push_back(me);
}
return out;
}
const int what_best = 3;
vector<pair<int, op_info> > get_best_split(vector<int> &poss) {
// try all operations of type 1-3
vector<pair<int, op_info> > good_tries;
for (auto op : threes) {
for (int typ = 1; typ <= 3; typ++) {
auto splits = get_split(typ, poss, op);
int cmxmin = max({splits[0].size(), splits[1].size(), splits[2].size()});
if (good_tries.size() < what_best || good_tries.back().first > cmxmin)
{
good_tries.emplace_back(cmxmin, op_info(typ, op));
sort(all(good_tries));
if (good_tries.size() > what_best)
good_tries.pop_back();
}
}
}
// try type 4
for (auto op : fours) {
auto splits = get_split(4, poss, op);
int cmxmin = max({splits[0].size(), splits[1].size(), splits[2].size()});
if (good_tries.size() < what_best || good_tries.back().first > cmxmin)
{
good_tries.emplace_back(cmxmin, op_info(4, op));
sort(all(good_tries));
if (good_tries.size() > what_best)
good_tries.pop_back();
}
}
return good_tries;
}
map<vector<int>, int> dp;
// returns depth
int build_tree(vector<int> poss) {
if (dp.find(poss) != dp.end())
return dp[poss] + 1;
if (poss.size() == 0)
return 0;
if (poss.size() == 1)
return 1;
vector<pair<int, op_info> > best_ops = get_best_split(poss);
op_info bst; int dpth = INF;
for (auto [useless, op] : best_ops) {
auto splits = get_split(op.first, poss, op.second);
int actual_depth = 0;
for (auto splt : splits)
actual_depth = max(actual_depth, build_tree(splt));
if (actual_depth < dpth)
dpth = actual_depth, bst = op;
}
best_op[poss] = bst;
dp[poss] = dpth;
return dpth + 1;
}
void init(int T) {
get_guys(1, 3, vector<int>(), threes);
for (auto vec : threes) {
for (int j = 1; j <= num_coins; j++) {
if (count(all(vec), j) == 0)
{
auto me = vec;
vec.push_back(j);
fours.push_back(vec);
}
}
}
vector<int> perm(6);
iota(all(perm), 1);
do {
perm_to_idx[perm] = perms.size();
perms.push_back(perm);
} while (next_permutation(all(perm)));
vector<int> strt(720);
iota(all(strt), 0);
build_tree(strt);
/*for (auto [a, b] : best_op) {
cout << "{{";
cout << a[0];
for (int i = 1; i < a.size(); i++)
cout << "," << a[i];
cout << "},";
cout << "op_info(";
cout << b.first << ",";
cout << "{";
cout << b.second[0];
for (int i = 1; i < b.second.size(); i++)
cout << "," << b.second[i];
cout << "})},";
}*/
}
void orderCoins() {
/* ... */
vector<int> poss(720);
iota(all(poss), 0);
//cout << best_op.size() << "\n";
while (poss.size() > 1)
{
op_info to_do = best_op[poss];
int out;
int a = to_do.second[0], b = to_do.second[1], c = to_do.second[2];
if (to_do.first <= 3) {
if (to_do.first == 1)
out = getHeaviest(a, b, c);
else if (to_do.first == 2)
out = getLightest(a, b, c);
else
out = getMedian(a, b, c);
} else {
out = getNextLightest(a, b, c, to_do.second[3]);
}
vector<vector<int> > split = get_split(to_do.first, poss, to_do.second);
if (out == a)
poss = split[0];
else if (out == b)
poss = split[1];
else if (out == c)
poss = split[2];
}
int W[6];
for (int i = 0; i < 6; i++)
W[i] = perms[poss[0]][i];
answer(W);
}
