#include "scales.h"
#include <bits/stdc++.h>
#define all(a) a.begin(), a.end()
using namespace std;
typedef pair<int, int> pii;
const int num_coins = 6;
const int INF = 1e9;
vector<vector<int> > threes, fours;
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);
}
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);
}
}
}
}
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<vector<int> > > get_split(int op_type, vector<vector<int> > &poss, vector<int> &op) {
vector<vector<vector<int> > > out(3);
for (vector<int> me : poss) {
int outcome = get_outcome(op_type, op, 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;
}
pair<int, vector<int> > get_best_split(vector<vector<int> > &poss) {
// try all operations of type 1-3
pair<int, vector<int> > bst; int max_min = INF;
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 (cmxmin < max_min)
bst = pair<int, vector<int> > (typ, op), max_min = cmxmin;
}
}
for (auto op : fours) {
auto splits = get_split(4, poss, op);
int cmxmin = max({splits[0].size(), splits[1].size(), splits[2].size()});
if (cmxmin < max_min)
bst = pair<int, vector<int> > (4, op), max_min = cmxmin;
}
return bst;
}
void orderCoins() {
/* ... */
vector<vector<int> > poss;
vector<int> perm(6);
iota(all(perm), 1);
do {
poss.push_back(perm);
} while (next_permutation(all(perm)));
while (poss.size() > 1)
{
pair<int, vector<int> > to_do = get_best_split(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<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] = poss[0][i];
answer(W);
}
