#include "scales.h"
#include <bits/stdc++.h>
using namespace std;
int lim[] = {1, 3, 9, 27, 81, 243, 729};
struct Ord {
int a[7];
Ord(vector<int>& v) {
for (int i = 0; i < 6; i++) a[i + 1] = v[i];
}
};
struct Query {
int a, b, c, d;
int ask() {
int res;
if (d == a) res = getLightest(a, b, c);
else if (d == b) res = getMedian(a, b, c);
else if (d == c) res = getHeaviest(a, b, c);
else res = getNextLightest(a, b, c, d);
if (res == a) return 1;
if (res == b) return 2;
if (res == c) return 3;
}
int simulate(Ord& ord) {
int i = a, j = b, l = c, res;
if (ord.a[i] > ord.a[j]) swap(i, j);
if (ord.a[j] > ord.a[l]) swap(j, l);
if (ord.a[i] > ord.a[j]) swap(i, j);
if (a == d) res = i;
else if (b == d) res = j;
else if (c == d) res = l;
else if (ord.a[d] < ord.a[i]) res = i;
else if (ord.a[d] < ord.a[j]) res = j;
else if (ord.a[d] < ord.a[l]) res = l;
else res = i;
if (res == a) return 1;
if (res == b) return 2;
if (res == c) return 3;
}
};
vector<Query> all_queries;
struct State {
int rem;
vector<Ord*> possible;
Query* opt;
State* children[4];
bool init() {
if (possible.size() <= 1) return true;
int cnt[4];
for (Query& q : all_queries) {
cnt[1] = cnt[2] = cnt[3] = 0;
for (Ord*& o : possible) {
int res = q.simulate(*o);
cnt[res]++;
if (cnt[res] > lim[rem]) break;
}
if (max({cnt[1], cnt[2], cnt[3]}) > lim[rem]) continue;
for (int i = 1; i < 4; i++) {
children[i] = new State();
children[i]->rem = rem - 1;
}
for (Ord* o : possible) children[q.simulate(*o)]->possible.push_back(o);
bool good = true;
for (int i = 1; i < 4; i++) good &= children[i]->init();
if (!good) {
for (int i = 1; i < 4; i++) delete children[i];
} else {
opt = &q;
return true;
}
}
return false;
}
} *root;
void init(int T) {
for (int i = 1; i < 5; i++)
for (int j = i + 1; j < 6; j++)
for (int k = j + 1; k < 7; k++)
for (int l = 1; l < 7; l++) all_queries.push_back({i, j, k, l});
root = new State();
root->rem = 5;
vector<int> curr_perm = {1, 2, 3, 4, 5, 6};
do {
root->possible.push_back(new Ord(curr_perm));
} while (next_permutation(curr_perm.begin(), curr_perm.end()));
assert(root->init());
}
void orderCoins() {
int W[] = {1, 2, 3, 4, 5};
State *ans = root;
while (ans->possible.size() > 1) ans = ans->children[ans->opt->ask()];
for (int i = 1; i <= 6; i++) W[ans->possible[0]->a[i] - 1] = i;
answer(W);
}
Compilation message
scales.cpp: In function 'void init(int)':
scales.cpp:88:15: warning: unused parameter 'T' [-Wunused-parameter]
88 | void init(int T) {
| ~~~~^
scales.cpp: In member function 'int Query::simulate(Ord&)':
scales.cpp:44:5: warning: control reaches end of non-void function [-Wreturn-type]
44 | }
| ^
scales.cpp: In member function 'int Query::ask()':
scales.cpp:27:5: warning: control reaches end of non-void function [-Wreturn-type]
27 | }
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
640 KB |
Output is correct |
2 |
Correct |
14 ms |
640 KB |
Output is correct |
3 |
Correct |
15 ms |
640 KB |
Output is correct |
4 |
Correct |
14 ms |
640 KB |
Output is correct |
5 |
Correct |
15 ms |
640 KB |
Output is correct |
6 |
Correct |
14 ms |
640 KB |
Output is correct |
7 |
Correct |
15 ms |
640 KB |
Output is correct |
8 |
Correct |
14 ms |
640 KB |
Output is correct |
9 |
Correct |
15 ms |
640 KB |
Output is correct |
10 |
Correct |
14 ms |
640 KB |
Output is correct |
11 |
Correct |
14 ms |
632 KB |
Output is correct |
12 |
Correct |
15 ms |
624 KB |
Output is correct |
13 |
Correct |
14 ms |
640 KB |
Output is correct |
14 |
Correct |
15 ms |
640 KB |
Output is correct |
15 |
Correct |
14 ms |
640 KB |
Output is correct |
16 |
Correct |
15 ms |
640 KB |
Output is correct |
17 |
Correct |
15 ms |
640 KB |
Output is correct |
18 |
Correct |
15 ms |
640 KB |
Output is correct |
19 |
Correct |
15 ms |
640 KB |
Output is correct |
20 |
Correct |
15 ms |
632 KB |
Output is correct |
21 |
Correct |
15 ms |
640 KB |
Output is correct |
22 |
Correct |
14 ms |
640 KB |
Output is correct |
23 |
Correct |
15 ms |
640 KB |
Output is correct |
24 |
Correct |
15 ms |
768 KB |
Output is correct |
25 |
Correct |
15 ms |
640 KB |
Output is correct |
26 |
Correct |
15 ms |
640 KB |
Output is correct |
27 |
Correct |
14 ms |
640 KB |
Output is correct |
28 |
Correct |
14 ms |
640 KB |
Output is correct |
29 |
Correct |
14 ms |
640 KB |
Output is correct |
30 |
Correct |
15 ms |
768 KB |
Output is correct |
31 |
Correct |
15 ms |
768 KB |
Output is correct |
32 |
Correct |
14 ms |
640 KB |
Output is correct |
33 |
Correct |
14 ms |
640 KB |
Output is correct |
34 |
Correct |
14 ms |
640 KB |
Output is correct |
35 |
Correct |
14 ms |
640 KB |
Output is correct |
36 |
Correct |
15 ms |
640 KB |
Output is correct |
37 |
Correct |
14 ms |
640 KB |
Output is correct |
38 |
Correct |
14 ms |
632 KB |
Output is correct |
39 |
Correct |
14 ms |
640 KB |
Output is correct |
40 |
Correct |
14 ms |
640 KB |
Output is correct |