#include "scales.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define fr first
#define se second
struct Query {
array<int, 3> vals = {0, 0, 0};
int t = 0, d = 0;
// 1 is light, 2 is heavy, 3 is median, and 4 is the lightest greater
bool operator<(const Query& a) const {
return false;
}
bool operator>(const Query& a) const {
return false;
}
};
Query start;
vector<Query> allQueries;
void init(int T) {
// pergunta inicial
start.t = 1;
start.vals = {4, 5, 6};
// ok
vector<int> n3 = {0, 0, 0, 1, 1, 1};
vector<int> n4 = {0, 0, 1, 1, 1, 2};
// find all of 3 type
do {
Query q;
int cnt = 0;
for (int i = 0; i < 6; i++) if (n3[i]) q.vals[cnt++] = (i + 1);
q.t = 1;
allQueries.push_back(q);
q.t = 2;
allQueries.push_back(q);
q.t = 3;
allQueries.push_back(q);
} while (next_permutation(n3.begin(), n3.end()));
do {
Query q;
int cnt = 0;
for (int i = 0; i < 6; i++) if (n4[i]) {
if (n4[i] < 2) q.vals[cnt++] = (i + 1);
else q.d = i + 1;
}
q.t = 4;
allQueries.push_back(q);
} while (next_permutation(n4.begin(), n4.end()));
}
int ans(array<int, 6>& perm, Query& q) {
array<pii, 3> ord;
for (int i = 0; i < 3; i++) ord[i] = {perm[q.vals[i] - 1], q.vals[i]};
sort(ord.begin(), ord.end());
if (q.t == 1) return ord[0].se;
if (q.t == 2) return ord[2].se;
if (q.t == 3) return ord[1].se;
for (int i = 0; i < 3; i++) if (perm[q.d - 1] < ord[i].fr) return ord[i].se;
return ord[0].se;
}
Query bst(vector<array<int, 6>>& pos) {
pair<int, Query> mi = {1e9, Query()};
for (auto u : allQueries) {
vector<int> amnt(7);
for (auto p : pos) amnt[ans(p, u)]++;
int mic = *max_element(amnt.begin(), amnt.end());
mi = min(mi, {mic, u});
}
return mi.se;
}
vector<array<int, 6>> re(int result, Query& q, vector<array<int, 6>>& pos) {
vector<array<int, 6>> withval;
for (auto u : pos) if (ans(u, q) == result) withval.push_back(u);
return withval;
}
vector<vector<array<int, 6>>> reAll(Query& q, vector<array<int, 6>>& pos) {
vector<vector<array<int, 6>>> withval(7);
for (auto u : pos) withval[ans(u, q)].push_back(u);
return withval;
}
int askQuery(Query q) {
if (q.t == 1) return getLightest(q.vals[0], q.vals[1], q.vals[2]);
if (q.t == 2) return getHeaviest(q.vals[0], q.vals[1], q.vals[2]);
if (q.t == 3) return getMedian(q.vals[0], q.vals[1], q.vals[2]);
return getNextLightest(q.vals[0], q.vals[1], q.vals[2], q.d);
}
int contador = 0;
pair<int, Query> bestBrute(vector<array<int, 6>> pos, int h) {
if (pos.size() == 1) return {h, Query()};
if (h == 5) return {7, Query()};
pair<int, Query> mi = {7, Query()};
for (auto u : allQueries) {
int t = pos.size();
vector<vector<array<int, 6>>> withval = reAll(u, pos);
int tammx = 0;
for (auto u : withval) tammx = max(tammx, ((int)u.size()));
if (tammx == t) continue;
int mx = 0;
for (auto u : withval) if (!u.empty()) mx = max(mx, bestBrute(u, h + 1).fr);
mi = min(mi, {mx, u});
}
return mi;
}
void orderCoins() {
// all perms
vector<array<int, 6>> pos;
array<int, 6> perm;
for (int i = 1; i <= 6; i++) perm[i - 1] = i;
do {
pos.push_back(perm);
} while (next_permutation(perm.begin(), perm.end()));
// ok
pos = re(askQuery(start), start, pos);
int h = 1;
bool badidea = 0;
while (((int) pos.size()) > 1) {
Query q = bst(pos);
if ((h >= 3) && !badidea) {
pair<int, Query> p = bestBrute(pos, h);
if (p.fr > 5) badidea = 1;
else q = p.se;
}
pos = re(askQuery(q), q, pos);
h++;
}
perm = pos[0];
int w[] = {0, 0, 0, 0, 0, 0};
for (int i = 0; i < 6; i++) {
int pomx = (min_element(perm.begin(), perm.end()) - perm.begin());
w[i] = (pomx + 1);
perm[pomx] = 1e9;
}
answer(w);
return;
}
