#include <bits/stdc++.h>
#include "scales.h"
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;
mt19937 rng(time(0));
map<vvi, pair<int, vi>> startegy_tree;
//type 1 = light,
// 2 = heavy,
// 3 = med,
// 4 = next
bool Solve(vvi &permutations, int x) {
if (permutations.size() <= 1) return true;
int log3 = 0;
int n = permutations.size();
for (int i = 1; i < n; i *= 3, log3++);
chkmax(x, 6 - log3);
if (x + log3 > 6) return false;
sort(all(permutations));
if (startegy_tree.count(permutations)) return true;
for (int a = 1; a <= 6; a++) {
for (int b = a + 1; b <= 6; b++) {
for (int c = b + 1; c <= 6; c++) {
vvi v1, v2, v3;
for (vi &v : permutations) {
int ind1, ind2, ind3;
for (ind1 = 0; v[ind1] != a; ind1++);
for (ind2 = 0; v[ind2] != b; ind2++);
for (ind3 = 0; v[ind3] != c; ind3++);
int i = min({ind1, ind2, ind3});
if (i == ind1) v1.push_back(v);
else if (i == ind2) v2.push_back(v);
else v3.push_back(v);
}
if (Solve(v1, x + 1) && Solve(v2, x + 1) && Solve(v3, x + 1)) {
if (!x) {
cout << "";
}
startegy_tree[permutations] = {1, {a, b, c}};
return true;
}
}
}
}
for (int a = 1; a <= 6; a++) {
for (int b = a + 1; b <= 6; b++) {
for (int c = b + 1; c <= 6; c++) {
vvi v1, v2, v3;
for (vi &v : permutations) {
int ind1, ind2, ind3;
for (ind1 = 0; v[ind1] != a; ind1++);
for (ind2 = 0; v[ind2] != b; ind2++);
for (ind3 = 0; v[ind3] != c; ind3++);
int i = max({ind1, ind2, ind3});
if (i == ind1) v1.push_back(v);
else if (i == ind2) v2.push_back(v);
else v3.push_back(v);
}
if (Solve(v1, x + 1) && Solve(v2, x + 1) && Solve(v3, x + 1)) {
if (!x) {
cout << "";
}
startegy_tree[permutations] = {2, {a, b, c}};
return true;
}
}
}
}
for (int a = 1; a <= 6; a++) {
for (int b = a + 1; b <= 6; b++) {
for (int c = b + 1; c <= 6; c++) {
vvi v1, v2, v3;
for (vi &v : permutations) {
int ind1, ind2, ind3;
for (ind1 = 0; v[ind1] != a; ind1++);
for (ind2 = 0; v[ind2] != b; ind2++);
for (ind3 = 0; v[ind3] != c; ind3++);
int i = max({ind1, ind2, ind3}), j = min({ind1, ind2, ind3});
if (i != ind1 && j != ind1) v1.push_back(v);
else if (i != ind2 && j != ind2) v2.push_back(v);
else v3.push_back(v);
}
if (Solve(v1, x + 1) && Solve(v2, x + 1) && Solve(v3, x + 1)) {
if (!x) {
cout << "";
}
startegy_tree[permutations] = {3, {a, b, c}};
return true;
}
}
}
}
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;
vvi v1, v2, v3;
for (vi &v : permutations) {
int ind;
for (ind = 0; v[ind] != d; ind++);
for (; v[ind] != a && v[ind] != b && v[ind] != c; ind++, ind %= 6);
if (v[ind] == a) v1.push_back(v);
else if (v[ind] == b) v2.push_back(v);
else v3.push_back(v);
}
if (Solve(v1, x + 1) && Solve(v2, x + 1) && Solve(v3, x + 1)) {
if (!x) {
cout << "";
}
startegy_tree[permutations] = {4, {a, b, c, d}};
return true;
}
}
}
}
}
if (!x) {
cout << "";
}
return false;
}
void init(int T) {
vvi permutations;
vi v = {1, 2, 3, 4, 5, 6};
do {
permutations.push_back(v);
} while (next_permutation(all(v)));
Solve(permutations, 0);
}
map<vi, int> asksLight;
int queryLight(int a, int b, int c) {
vi v = {a, b, c};
sort(all(v));
if (asksLight.count(v)) return asksLight[v];
return asksLight[v] = getLightest(a, b, c);
}
map<vi, int> asksHeavy;
int queryHeavy(int a, int b, int c) {
vi v = {a, b, c};
sort(all(v));
if (asksHeavy.count(v)) return asksHeavy[v];
return asksHeavy[v] = getHeaviest(a, b, c);
}
map<vi, int> asksMed;
int queryMed(int a, int b, int c) {
vi v = {a, b, c};
sort(all(v));
if (asksMed.count(v)) return asksMed[v];
return asksMed[v] = getMedian(a, b, c);
}
map<vi, int> asksNext;
int queryNext(int a, int b, int c, int d) {
vi v = {a, b, c};
sort(all(v));
v.push_back(d);
if (asksNext.count(v)) return asksNext[v];
return asksNext[v] = getNextLightest(a, b, c, d);
}
void orderCoins() {
int w[] = {1, 2, 3, 4, 5, 6};
asksLight.clear();
asksHeavy.clear();
asksMed.clear();
asksNext.clear();
vvi permutations;
vi v = {1, 2, 3, 4, 5, 6};
do {
permutations.push_back(v);
} while (next_permutation(all(v)));
while (permutations.size() > 1) {
int n = permutations.size();
sort(all(permutations));
auto [type, v] = startegy_tree[permutations];
int a = v[0], b = v[1], c = v[2];
vvi next;
if (type == 1) {
int x = queryLight(a, b, c);
for (vi &v : permutations) {
int ind1, ind2, ind3;
for (ind1 = 0; v[ind1] != a; ind1++);
for (ind2 = 0; v[ind2] != b; ind2++);
for (ind3 = 0; v[ind3] != c; ind3++);
if (v[min({ind1, ind2, ind3})] == x) next.push_back(v);
}
} else if (type == 2) {
int x = queryHeavy(a, b, c);
for (vi &v : permutations) {
int ind1, ind2, ind3;
for (ind1 = 0; v[ind1] != a; ind1++);
for (ind2 = 0; v[ind2] != b; ind2++);
for (ind3 = 0; v[ind3] != c; ind3++);
if (v[max({ind1, ind2, ind3})] == x) next.push_back(v);
}
} else if (type == 3) {
int x = queryMed(a, b, c);
if (x == b) swap(a, b);
if (x == c) swap(a, c);
for (vi &v : permutations) {
int ind1, ind2, ind3;
for (ind1 = 0; v[ind1] != a; ind1++);
for (ind2 = 0; v[ind2] != b; ind2++);
for (ind3 = 0; v[ind3] != c; ind3++);
if (ind1 != max({ind1, ind2, ind3}) && ind1 != min({ind1, ind2, ind3})) next.push_back(v);
}
} else {
int d = v[3];
int x = queryNext(a, b, c, d);
for (vi &v : permutations) {
int ind;
for (ind = 0; v[ind] != d; ind++);
for (; v[ind] != a && v[ind] != b && v[ind] != c; ind++, ind %= 6);
if (v[ind] == x) next.push_back(v);
}
}
swap(permutations, next);
}
for (int i = 0; i < 6; i++) w[i] = permutations[0][i];
answer(w);
}
Compilation message
scales.cpp: In function 'bool Solve(vvi&, int)':
scales.cpp:26:30: warning: conversion from 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
26 | int n = permutations.size();
| ~~~~~~~~~~~~~~~~~^~
scales.cpp: In function 'void init(int)':
scales.cpp:135:15: warning: unused parameter 'T' [-Wunused-parameter]
135 | void init(int T) {
| ~~~~^
scales.cpp: In function 'void orderCoins()':
scales.cpp:189:34: warning: conversion from 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
189 | int n = permutations.size();
| ~~~~~~~~~~~~~~~~~^~
scales.cpp:191:21: warning: declaration of 'v' shadows a previous local [-Wshadow]
191 | auto [type, v] = startegy_tree[permutations];
| ^
scales.cpp:184:8: note: shadowed declaration is here
184 | vi v = {1, 2, 3, 4, 5, 6};
| ^
scales.cpp:196:22: warning: declaration of 'v' shadows a previous local [-Wshadow]
196 | for (vi &v : permutations) {
| ^
scales.cpp:191:21: note: shadowed declaration is here
191 | auto [type, v] = startegy_tree[permutations];
| ^
scales.cpp:205:22: warning: declaration of 'v' shadows a previous local [-Wshadow]
205 | for (vi &v : permutations) {
| ^
scales.cpp:191:21: note: shadowed declaration is here
191 | auto [type, v] = startegy_tree[permutations];
| ^
scales.cpp:216:22: warning: declaration of 'v' shadows a previous local [-Wshadow]
216 | for (vi &v : permutations) {
| ^
scales.cpp:191:21: note: shadowed declaration is here
191 | auto [type, v] = startegy_tree[permutations];
| ^
scales.cpp:226:22: warning: declaration of 'v' shadows a previous local [-Wshadow]
226 | for (vi &v : permutations) {
| ^
scales.cpp:191:21: note: shadowed declaration is here
191 | auto [type, v] = startegy_tree[permutations];
| ^
scales.cpp:189:13: warning: unused variable 'n' [-Wunused-variable]
189 | int n = permutations.size();
| ^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
407 ms |
6920 KB |
Output is correct |
| 2 |
Correct |
402 ms |
7084 KB |
Output is correct |
| 3 |
Correct |
469 ms |
6980 KB |
Output is correct |
| 4 |
Correct |
396 ms |
6932 KB |
Output is correct |
| 5 |
Correct |
421 ms |
6932 KB |
Output is correct |
| 6 |
Correct |
412 ms |
7000 KB |
Output is correct |
| 7 |
Correct |
402 ms |
7020 KB |
Output is correct |
| 8 |
Correct |
427 ms |
7088 KB |
Output is correct |
| 9 |
Correct |
415 ms |
6968 KB |
Output is correct |
| 10 |
Correct |
396 ms |
6952 KB |
Output is correct |
| 11 |
Correct |
443 ms |
7000 KB |
Output is correct |
| 12 |
Correct |
407 ms |
6988 KB |
Output is correct |
| 13 |
Correct |
433 ms |
6992 KB |
Output is correct |
| 14 |
Correct |
393 ms |
6980 KB |
Output is correct |
| 15 |
Correct |
413 ms |
7080 KB |
Output is correct |
| 16 |
Correct |
454 ms |
7004 KB |
Output is correct |
| 17 |
Correct |
419 ms |
7076 KB |
Output is correct |
| 18 |
Correct |
413 ms |
7140 KB |
Output is correct |
| 19 |
Correct |
394 ms |
7020 KB |
Output is correct |
| 20 |
Correct |
443 ms |
6952 KB |
Output is correct |
| 21 |
Correct |
396 ms |
6956 KB |
Output is correct |
| 22 |
Correct |
430 ms |
7088 KB |
Output is correct |
| 23 |
Correct |
444 ms |
7004 KB |
Output is correct |
| 24 |
Correct |
405 ms |
6940 KB |
Output is correct |
| 25 |
Correct |
419 ms |
6980 KB |
Output is correct |
| 26 |
Correct |
406 ms |
6964 KB |
Output is correct |
| 27 |
Correct |
430 ms |
6976 KB |
Output is correct |
| 28 |
Correct |
409 ms |
7144 KB |
Output is correct |
| 29 |
Correct |
410 ms |
6968 KB |
Output is correct |
| 30 |
Correct |
422 ms |
7036 KB |
Output is correct |
| 31 |
Correct |
416 ms |
7016 KB |
Output is correct |
| 32 |
Correct |
404 ms |
6992 KB |
Output is correct |
| 33 |
Correct |
436 ms |
6956 KB |
Output is correct |
| 34 |
Correct |
391 ms |
6944 KB |
Output is correct |
| 35 |
Correct |
441 ms |
7044 KB |
Output is correct |
| 36 |
Correct |
415 ms |
6920 KB |
Output is correct |
| 37 |
Correct |
401 ms |
6940 KB |
Output is correct |
| 38 |
Correct |
415 ms |
7000 KB |
Output is correct |
| 39 |
Correct |
422 ms |
6972 KB |
Output is correct |
| 40 |
Correct |
413 ms |
7020 KB |
Output is correct |
