#include "scales.h"
#include <algorithm>
#include <vector>
using namespace std;
struct _qs {
int i, a, b, c, d;
int query() const {
if (i == 1) return getHeaviest(a + 1, b + 1, c + 1) - 1;
if (i == 2) return getLightest(a + 1, b + 1, c + 1) - 1;
if (i == 3) return getMedian(a + 1, b + 1, c + 1) - 1;
return getNextLightest(a + 1, b + 1, c + 1, d + 1) - 1;
}
int queryIdx() const {
int x = query();
if (x == a) return 1;
if (x == b) return 2;
return 3;
}
} qs[120];
struct arr {
int x[6];
int query1(int a, int b, int c) const {
int t = a;
if (x[t] < x[b]) t = b;
if (x[t] < x[c]) t = c;
return t;
}
int query2(int a, int b, int c) const {
int t = a;
if (x[b] < x[t]) t = b;
if (x[c] < x[t]) t = c;
return t;
}
int query3(int a, int b, int c) const {
return a + b + c - query1(a, b, c) - query2(a, b, c);
}
int query4(int a, int b, int c, int d) const {
vector<int> vt;
if (x[d] < x[a]) vt.push_back(a);
if (x[d] < x[b]) vt.push_back(b);
if (x[d] < x[c]) vt.push_back(c);
if (vt.empty()) return query2(a, b, c);
int t = vt[0];
for (int i = 1; i < vt.size(); ++i) {
if (x[vt[i]] < x[t]) t = vt[i];
}
return t;
}
int query(int i, int a, int b, int c, int d) const {
if (i == 1) return query1(a, b, c);
if (i == 2) return query2(a, b, c);
if (i == 3) return query3(a, b, c);
return query4(a, b, c, d);
}
int query(_qs q) const {
return query(q.i, q.a, q.b, q.c, q.d);
}
int queryIdx(_qs q) const {
int x = query(q);
if (x == q.a) return 1;
if (x == q.b) return 2;
return 3;
}
} as[720];
int ans[720][120];
int pow3[6];
int op[364];
bool dfs(int node, int dep, const vector<int> &vt) {
if (dep == 0) return 1;
for (int i = 0; i < 120; ++i) {
vector<int> v[4];
for (int j : vt) {
v[ans[j][i]].push_back(j);
}
int mx = 0;
for (int j = 1; j <= 3; ++j) {
mx = max(mx, (int)v[j].size());
}
if (pow3[dep - 1] < mx) continue;
int p = 1;
for (int j = 1; j <= 3; ++j) {
if (v[j].empty()) continue;
if (!dfs(3 * node + j, dep - 1, v[j])){
p = 0;
break;
}
}
if (p) {
op[node] = i;
return 1;
}
}
return 0;
}
void init(int T) {
pow3[0] = 1;
for (int i = 1; i < 6; ++i) pow3[i] = 3 * pow3[i - 1];
int p = 0;
for (int i = 0; i < 6; ++i) {
for (int j = i + 1; j < 6; ++j) {
for (int k = j + 1; k < 6; ++k) {
for (int t = 1; t <= 3; ++t) {
qs[p++] = { t, i, j, k, -1 };
}
}
}
}
for (int i = 0; i < 6; ++i) {
for (int j = i + 1; j < 6; ++j) {
for (int k = j + 1; k < 6; ++k) {
for (int t = 0; t < 6; ++t) {
if (i == t || j == t || k == t) continue;
qs[p++] = { 4, i, j, k, t };
}
}
}
}
for (int i = 0; i < 6; ++i) as[0].x[i] = i;
for (int i = 0; i < 720; ++i) {
if (i) {
for (int j = 0; j < 6; ++j) as[i].x[j] = as[i - 1].x[j];
next_permutation(as[i].x, as[i].x + 6);
}
for (int j = 0; j < 120; ++j) {
ans[i][j] = as[i].queryIdx(qs[j]);
}
}
vector<int> in;
for (int i = 0; i < 720; ++i) in.push_back(i);
if (!dfs(0, 6, in)) throw -1;
}
void orderCoins() {
int node = 0;
vector<int> in;
for (int i = 0; i < 720; ++i) in.push_back(i);
while (in.size() > 1) {
int x = op[node];
int ret = qs[x].queryIdx();
vector<int> tp;
for (int j : in) {
if (ans[j][x] == ret) tp.push_back(j);
}
node = 3 * node + ret;
in = tp;
}
int ret[6];
for (int i = 0; i < 6; ++i) ret[as[in[0]].x[i]] = i + 1;
answer(ret);
}
Compilation message
In file included from grader.c:2:0:
graderlib.c: In function 'void answer(int*)':
graderlib.c:53:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
if (_ghksjhdfkae19ga_ > 1)
^~
graderlib.c:56:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
for (i = 0; i < 6; i++) {
^~~
scales.cpp: In member function 'int arr::query4(int, int, int, int) const':
scales.cpp:47:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 1; i < vt.size(); ++i) {
~~^~~~~~~~~~~
scales.cpp: In member function 'int arr::queryIdx(_qs) const':
scales.cpp:62:13: warning: declaration of 'x' shadows a member of 'arr' [-Wshadow]
int x = query(q);
^
scales.cpp:24:12: note: shadowed declaration is here
int x[6];
^
scales.cpp: In function 'void init(int)':
scales.cpp:102:15: warning: unused parameter 'T' [-Wunused-parameter]
void init(int T) {
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
632 KB |
Output is correct |
| 2 |
Correct |
16 ms |
740 KB |
Output is correct |
| 3 |
Correct |
15 ms |
740 KB |
Output is correct |
| 4 |
Correct |
15 ms |
820 KB |
Output is correct |
| 5 |
Correct |
21 ms |
820 KB |
Output is correct |
| 6 |
Correct |
12 ms |
820 KB |
Output is correct |
| 7 |
Correct |
12 ms |
820 KB |
Output is correct |
| 8 |
Correct |
12 ms |
820 KB |
Output is correct |
| 9 |
Correct |
11 ms |
820 KB |
Output is correct |
| 10 |
Correct |
13 ms |
820 KB |
Output is correct |
| 11 |
Correct |
13 ms |
820 KB |
Output is correct |
| 12 |
Correct |
11 ms |
820 KB |
Output is correct |
| 13 |
Correct |
14 ms |
820 KB |
Output is correct |
| 14 |
Correct |
11 ms |
820 KB |
Output is correct |
| 15 |
Correct |
11 ms |
884 KB |
Output is correct |
| 16 |
Correct |
12 ms |
884 KB |
Output is correct |
| 17 |
Correct |
14 ms |
884 KB |
Output is correct |
| 18 |
Correct |
11 ms |
884 KB |
Output is correct |
| 19 |
Correct |
11 ms |
884 KB |
Output is correct |
| 20 |
Correct |
11 ms |
884 KB |
Output is correct |
| 21 |
Correct |
11 ms |
896 KB |
Output is correct |
| 22 |
Correct |
16 ms |
896 KB |
Output is correct |
| 23 |
Correct |
19 ms |
896 KB |
Output is correct |
| 24 |
Correct |
12 ms |
896 KB |
Output is correct |
| 25 |
Correct |
11 ms |
896 KB |
Output is correct |
| 26 |
Correct |
12 ms |
944 KB |
Output is correct |
| 27 |
Correct |
15 ms |
944 KB |
Output is correct |
| 28 |
Correct |
21 ms |
944 KB |
Output is correct |
| 29 |
Correct |
11 ms |
944 KB |
Output is correct |
| 30 |
Correct |
12 ms |
944 KB |
Output is correct |
| 31 |
Correct |
11 ms |
944 KB |
Output is correct |
| 32 |
Correct |
11 ms |
944 KB |
Output is correct |
| 33 |
Correct |
11 ms |
944 KB |
Output is correct |
| 34 |
Correct |
11 ms |
944 KB |
Output is correct |
| 35 |
Correct |
11 ms |
944 KB |
Output is correct |
| 36 |
Correct |
12 ms |
944 KB |
Output is correct |
| 37 |
Correct |
11 ms |
944 KB |
Output is correct |
| 38 |
Correct |
13 ms |
944 KB |
Output is correct |
| 39 |
Correct |
11 ms |
944 KB |
Output is correct |
| 40 |
Correct |
13 ms |
944 KB |
Output is correct |
