#include "scales.h"
#include <bits/stdc++.h>
using namespace std;
vector <int> ve[720];
int pos[720][7];
const int N = 6;
void init(int T) {
vector <int> p = {1, 2, 3, 4, 5, 6};
for (int i = 0; i < 720; i++) {
ve[i] = p;
for (int j = 0; j < 6; j++) pos[i][p[j]] = j;
next_permutation(p.begin(), p.end());
}
}
int res;
void solve(vector <int> &candidate) {
// cerr << candidate.size() << '\n';
if (candidate.size() == 1) {
res = candidate[0];
return;
}
int mi[4] = {int(2e9), int(2e9), int(2e9), int(2e9)};
vector <int> triple[4];
for (int a = 1; a <= 6; a++)
for (int b = a + 1; b <= 6; b++)
for (int c = b + 1; c <= 6; c++) {
// ask query 1: which is heaviest
int cntA = 0, cntB = 0, cntC = 0;
for (int id: candidate) {
int tmp = max({pos[id][a], pos[id][b], pos[id][c]});
if (tmp == pos[id][a]) ++cntA;
if (tmp == pos[id][b]) ++cntB;
if (tmp == pos[id][c]) ++cntC;
}
int worst = max({cntA, cntB, cntC});
if (worst < mi[0]) mi[0] = worst, triple[0] = {a, b, c};
// ask query 2: which is lightest
cntA = 0, cntB = 0, cntC = 0;
for (int id: candidate) {
int tmp = min({pos[id][a], pos[id][b], pos[id][c]});
if (tmp == pos[id][a]) ++cntA;
if (tmp == pos[id][b]) ++cntB;
if (tmp == pos[id][c]) ++cntC;
}
worst = max({cntA, cntB, cntC});
if (worst < mi[1]) mi[1] = worst, triple[1] = {a, b, c};
// ask query 3: which is median
cntA = 0, cntB = 0, cntC = 0;
for (int id: candidate) {
int minn = min({pos[id][a], pos[id][b], pos[id][c]});
int maxx = max({pos[id][a], pos[id][b], pos[id][c]});
if (pos[id][a] != minn && pos[id][a] != maxx) ++cntA;
if (pos[id][b] != minn && pos[id][b] != maxx) ++cntB;
if (pos[id][c] != minn && pos[id][c] != maxx) ++cntC;
}
worst = max({cntA, cntB, cntC});
if (worst < mi[2]) mi[2] = worst, triple[2] = {a, b, c};
}
// ask query 4: which is the lighest such that heavier d
for (int a = 1; a <= 6; a++)
for (int b = a + 1; b <= 6; b++)
for (int c = b + 1; c <= 6; c++)
for (int d = 1; d <= 6; d++) {
if (d == a || d == b || d == c) continue;
int cntA = 0, cntB = 0, cntC = 0;
for (int id: candidate) {
int posd = pos[id][d], tmp = 2e9;
if (pos[id][a] > posd) tmp = min(tmp, pos[id][a]);
if (pos[id][b] > posd) tmp = min(tmp, pos[id][b]);
if (pos[id][c] > posd) tmp = min(tmp, pos[id][c]);
if (tmp == 2e9)
tmp = min({pos[id][a], pos[id][b], pos[id][c]});
if (pos[id][a] == tmp) ++cntA;
if (pos[id][b] == tmp) ++cntB;
if (pos[id][c] == tmp) ++cntC;
}
int worst = max({cntA, cntB, cntC});
if (worst < mi[3]) mi[3] = worst, triple[3] = {a, b, c, d};
}
int best = min({mi[0], mi[1], mi[2], mi[3]});
vector <int> child;
if (best == mi[0]) {
int a = triple[0][0], b = triple[0][1], c = triple[0][2];
int ans = getHeaviest(a, b, c);
for (int id: candidate) {
int tmp = max({pos[id][a], pos[id][b], pos[id][c]});
if (tmp == pos[id][ans]) child.emplace_back(id);
}
}
else if (best == mi[1]) {
int a = triple[1][0], b = triple[1][1], c = triple[1][2];
int ans = getLightest(a, b, c);
for (int id: candidate) {
int tmp = min({pos[id][a], pos[id][b], pos[id][c]});
if (tmp == pos[id][ans]) child.emplace_back(id);
}
}
else if (best == mi[2]) {
int a = triple[2][0], b = triple[2][1], c = triple[2][2];
int ans = getMedian(a, b, c);
for (int id: candidate) {
int minn = min({pos[id][a], pos[id][b], pos[id][c]});
int maxx = max({pos[id][a], pos[id][b], pos[id][c]});
// cerr << minn << ' ' << maxx << '\n';
if (pos[id][ans] != minn && pos[id][ans] != maxx)
child.emplace_back(id);
}
}
else {
int a = triple[3][0], b = triple[3][1], c = triple[3][2], d = triple[3][3];
int ans = getNextLightest(a, b, c, d);
// cerr << a << ' ' << b << ' ' << c << ' ' << d << '\n';
for (int id: candidate) {
int posd = pos[id][d], tmp = 2e9;
if (pos[id][a] > posd) tmp = min(tmp, pos[id][a]);
if (pos[id][b] > posd) tmp = min(tmp, pos[id][b]);
if (pos[id][c] > posd) tmp = min(tmp, pos[id][c]);
if (tmp == 2e9)
tmp = min({pos[id][a], pos[id][b], pos[id][c]});
if (pos[id][ans] == tmp) child.emplace_back(id);
}
}
solve(child);
}
void orderCoins() {
vector <int> candidate(720);
iota(candidate.begin(), candidate.end(), 0);
solve(candidate);
int ans[6] = {};
for (int i = 0; i < 6; i++)
ans[i] = ve[res][i];
answer(ans);
}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
