//Solution by: LLM
#include <bits/stdc++.h>
#include "scales.h"
using namespace std;
#define FOR(i, l, r) for(int i = l; i <= r; i++)
#define pb push_back
vector<vector<int>> perms;
struct Query {
char type;
int a, b, c, d;
};
vector<Query> all_queries;
vector<vector<int>> precomp;
map<vector<int>, int> best_query; // Maps a state to the index of the optimal query
int simulate(const Query& q, const vector<int>& p) {
int wa = find(p.begin(), p.end(), q.a) - p.begin();
int wb = find(p.begin(), p.end(), q.b) - p.begin();
int wc = find(p.begin(), p.end(), q.c) - p.begin();
vector<pair<int, int>> w = {{wa, q.a}, {wb, q.b}, {wc, q.c}};
sort(w.begin(), w.end());
int ans_coin = 0;
if (q.type == 'L') ans_coin = w[0].second;
else if (q.type == 'H') ans_coin = w[2].second;
else if (q.type == 'M') ans_coin = w[1].second;
else if (q.type == 'N') {
int wd = find(p.begin(), p.end(), q.d) - p.begin();
ans_coin = -1;
FOR(i, 0, 2) {
if (w[i].first > wd) {
ans_coin = w[i].second;
break;
}
}
if (ans_coin == -1) ans_coin = w[0].second;
}
if (ans_coin == q.a) return 0;
if (ans_coin == q.b) return 1;
return 2;
}
// 1. Build the data structures once
void init(int T) {
vector<int> p = {1, 2, 3, 4, 5, 6};
do { perms.pb(p); } while (next_permutation(p.begin(), p.end()));
FOR(a, 1, 6) FOR(b, a + 1, 6) FOR(c, b + 1, 6) {
all_queries.pb({'L', a, b, c, 0});
all_queries.pb({'H', a, b, c, 0});
all_queries.pb({'M', a, b, c, 0});
FOR(d, 1, 6) {
if (d != a && d != b && d != c) all_queries.pb({'N', a, b, c, d});
}
}
precomp.assign(all_queries.size(), vector<int>(perms.size()));
FOR(i, 0, (int)all_queries.size() - 1) {
FOR(j, 0, (int)perms.size() - 1) {
precomp[i][j] = simulate(all_queries[i], perms[j]);
}
}
}
// 2. The core DFS (returns true if this state is solvable)
bool dfs(vector<int>& cands, int depth) {
if (cands.size() <= 1) return true;
int p3 = 1; FOR(i, 1, 6 - depth) p3 *= 3;
if (cands.size() > p3) return false; // Math pruning
if (best_query.count(cands)) return best_query[cands] != -1;
FOR(i, 0, (int)all_queries.size() - 1) {
vector<int> buckets[3];
for (int idx : cands) buckets[precomp[i][idx]].pb(idx);
if (buckets[0].size() == cands.size() ||
buckets[1].size() == cands.size() ||
buckets[2].size() == cands.size()) continue;
// If all 3 branches can be solved, we found our optimal query
if (dfs(buckets[0], depth + 1) && dfs(buckets[1], depth + 1) && dfs(buckets[2], depth + 1)) {
best_query[cands] = i;
return true;
}
}
best_query[cands] = -1; // Mark as unsolvable
return false;
}
// 3. Walk the tree dynamically based on Grader responses
void orderCoins() {
vector<int> cands(720);
iota(cands.begin(), cands.end(), 0);
int depth = 0;
while (cands.size() > 1) {
// Ensure we know the best move from here
dfs(cands, depth);
int q_idx = best_query[cands];
Query q = all_queries[q_idx];
// Actually ask the judge
int ans_coin;
if (q.type == 'L') ans_coin = getLightest(q.a, q.b, q.c);
else if (q.type == 'H') ans_coin = getHeaviest(q.a, q.b, q.c);
else if (q.type == 'M') ans_coin = getMedian(q.a, q.b, q.c);
else ans_coin = getNextLightest(q.a, q.b, q.c, q.d);
// Figure out which branch the judge's answer maps to
int branch = (ans_coin == q.a) ? 0 : (ans_coin == q.b) ? 1 : 2;
// Filter candidates and move to the next depth
vector<int> next_cands;
for (int idx : cands) {
if (precomp[q_idx][idx] == branch) next_cands.pb(idx);
}
cands = next_cands;
depth++;
}
// We isolated the exact permutation
vector<int> res = perms[cands[0]];
int W[] = {res[0], res[1], res[2], res[3], res[4], res[5]};
answer(W);
}
