#include "scales.h"
#include<bits/stdc++.h>
using namespace std;
mt19937 rng(1);
int n = 6;
int order[10];
vector<tuple<int, int, int> > three;
vector<tuple<int, int, int, int> > four;
void init(int T) {
for(int a = 1; a <= n; a++) for(int b = a + 1; b <= n; b++) for(int c = b + 1; c <= n; c++) {
three.emplace_back(a, b, c);
}
for(int d = 1; d <= n; d++) for(int a = 1; a <= n; a++) for(int b = a + 1; b <= n; b++) for(int c = b + 1; c <= n; c++) {
if (d != a && d != b && d != c) {
four.emplace_back(a, b, c, d);
}
}
}
int ask_three(int a, int b, int c, int type, vector<int> tmp) {
order[1] = a; order[2] = b; order[3] = c;
sort(order + 1, order + 4, [&] (const int &x, const int &y) {
return tmp[x] < tmp[y];
});
return order[type];
}
int ask_four(int a, int b, int c, int d, vector<int> tmp) {
int ret = 0;
tmp[0] = 1e9;
if (tmp[a] > tmp[d] && tmp[a] < tmp[ret]) ret = a;
if (tmp[b] > tmp[d] && tmp[b] < tmp[ret]) ret = b;
if (tmp[c] > tmp[d] && tmp[c] < tmp[ret]) ret = c;
if (ret == 0) return ask_three(a, b, c, 1, tmp);
return ret;
}
void orderCoins() {
shuffle(three.begin(), three.end(), rng);
shuffle(four.begin(), four.end(), rng);
vector<vector<int> > p;
for(int i = 1; i <= n; i++) order[i] = i;
do {
vector<int> tmp(n + 1);
for(int i = 1; i <= n; i++) tmp[i] = order[i];
p.push_back(tmp);
} while (next_permutation(order + 1, order + n + 1));
while (p.size() > 1) {
int best = 1e9;
int _a, _b, _c, _d, _t;
for(auto &[a, b, c, d] : four) {
int worst = 0;
for(int result = 1; result <= n; result++) {
int sat = 0;
for(auto &tmp : p) sat += result == ask_four(a, b, c, d, tmp);
if (sat) worst = max(worst, sat);
}
if (!worst) continue;
if (best > worst - 1) {
best = worst - 1;
_a = a;
_b = b;
_c = c;
_d = d;
_t = 0;
}
}
for(auto &[a, b, c] : three) for(int type = 1; type <= 3; type++) {
int worst = 0;
for(int result = 1; result <= n; result++) {
int sat = 0;
for(auto &tmp : p) sat += result == ask_three(a, b, c, type, tmp);
if (sat) worst = max(worst, sat);
}
if (!worst) continue;
if (best > worst) {
best = worst;
_a = a;
_b = b;
_c = c;
_t = type;
}
}
// if (best == p.size()) break;
assert(best < p.size());
#ifdef ngu
cout << _a << " " << _b << " " << _c << " " << _d << " " << _t << endl;
#endif // ngu
int result = 0;
vector<vector<int> > _p;
if (_t) {
if (_t == 1) result = getLightest(_a, _b, _c);
if (_t == 2) result = getMedian(_a, _b, _c);
if (_t == 3) result = getHeaviest(_a, _b, _c);
for(auto &tmp : p) if (ask_three(_a, _b, _c, _t, tmp) == result) {
_p.push_back(tmp);
}
assert(_p.size() < p.size());
p = _p;
}
else {
result = getNextLightest(_a, _b, _c, _d);
for(auto &tmp : p) if (ask_four(_a, _b, _c, _d, tmp) == result) {
_p.push_back(tmp);
}
assert(_p.size() < p.size());
p = _p;
}
}
vector<int> tmp = p.back();
int hidden[n];
for(int i = 1; i <= n; i++) hidden[tmp[i] - 1] = i;
#ifdef ngu
for(int i = 0; i < n; i++) cerr << hidden[i] << " ";
#endif // ngu
answer(hidden);
}
Compilation message
scales.cpp: In function 'void init(int)':
scales.cpp:14:15: warning: unused parameter 'T' [-Wunused-parameter]
14 | void init(int T) {
| ~~~~^
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from scales.cpp:2:
scales.cpp: In function 'void orderCoins()':
scales.cpp:96:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
96 | assert(best < p.size());
| ~~~~~^~~~~~~~~~
scales.cpp:105:7: warning: '_t' may be used uninitialized in this function [-Wmaybe-uninitialized]
105 | if (_t == 1) result = getLightest(_a, _b, _c);
| ^~
scales.cpp:117:38: warning: '_d' may be used uninitialized in this function [-Wmaybe-uninitialized]
117 | for(auto &tmp : p) if (ask_four(_a, _b, _c, _d, tmp) == result) {
| ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
scales.cpp:107:40: warning: '_c' may be used uninitialized in this function [-Wmaybe-uninitialized]
107 | if (_t == 3) result = getHeaviest(_a, _b, _c);
| ~~~~~~~~~~~^~~~~~~~~~~~
scales.cpp:107:40: warning: '_b' may be used uninitialized in this function [-Wmaybe-uninitialized]
scales.cpp:107:40: warning: '_a' may be used uninitialized in this function [-Wmaybe-uninitialized]
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
76 ms |
596 KB |
Execution killed with signal 6 |
| 2 |
Runtime error |
51 ms |
756 KB |
Execution killed with signal 6 |
| 3 |
Runtime error |
51 ms |
596 KB |
Execution killed with signal 6 |
| 4 |
Runtime error |
75 ms |
764 KB |
Execution killed with signal 6 |
| 5 |
Runtime error |
78 ms |
504 KB |
Execution killed with signal 6 |
| 6 |
Runtime error |
29 ms |
612 KB |
Execution killed with signal 6 |
| 7 |
Runtime error |
75 ms |
500 KB |
Execution killed with signal 6 |
| 8 |
Runtime error |
50 ms |
516 KB |
Execution killed with signal 6 |
| 9 |
Runtime error |
25 ms |
604 KB |
Execution killed with signal 6 |
| 10 |
Runtime error |
25 ms |
544 KB |
Execution killed with signal 6 |
| 11 |
Runtime error |
26 ms |
508 KB |
Execution killed with signal 6 |
| 12 |
Runtime error |
25 ms |
604 KB |
Execution killed with signal 6 |
| 13 |
Runtime error |
26 ms |
504 KB |
Execution killed with signal 6 |
| 14 |
Runtime error |
77 ms |
504 KB |
Execution killed with signal 6 |
| 15 |
Runtime error |
30 ms |
496 KB |
Execution killed with signal 6 |
| 16 |
Runtime error |
51 ms |
604 KB |
Execution killed with signal 6 |
| 17 |
Runtime error |
51 ms |
756 KB |
Execution killed with signal 6 |
| 18 |
Runtime error |
52 ms |
596 KB |
Execution killed with signal 6 |
| 19 |
Runtime error |
78 ms |
592 KB |
Execution killed with signal 6 |
| 20 |
Runtime error |
26 ms |
596 KB |
Execution killed with signal 6 |
| 21 |
Runtime error |
26 ms |
604 KB |
Execution killed with signal 6 |
| 22 |
Runtime error |
175 ms |
760 KB |
Execution killed with signal 6 |
| 23 |
Runtime error |
75 ms |
756 KB |
Execution killed with signal 6 |
| 24 |
Runtime error |
26 ms |
604 KB |
Execution killed with signal 6 |
| 25 |
Runtime error |
26 ms |
592 KB |
Execution killed with signal 6 |
| 26 |
Runtime error |
51 ms |
596 KB |
Execution killed with signal 6 |
| 27 |
Runtime error |
26 ms |
596 KB |
Execution killed with signal 6 |
| 28 |
Runtime error |
53 ms |
756 KB |
Execution killed with signal 6 |
| 29 |
Runtime error |
84 ms |
752 KB |
Execution killed with signal 6 |
| 30 |
Runtime error |
26 ms |
596 KB |
Execution killed with signal 6 |
| 31 |
Runtime error |
26 ms |
492 KB |
Execution killed with signal 6 |
| 32 |
Runtime error |
56 ms |
756 KB |
Execution killed with signal 6 |
| 33 |
Runtime error |
27 ms |
600 KB |
Execution killed with signal 6 |
| 34 |
Runtime error |
30 ms |
852 KB |
Execution killed with signal 6 |
| 35 |
Runtime error |
26 ms |
592 KB |
Execution killed with signal 6 |
| 36 |
Runtime error |
51 ms |
516 KB |
Execution killed with signal 6 |
| 37 |
Runtime error |
76 ms |
596 KB |
Execution killed with signal 6 |
| 38 |
Runtime error |
26 ms |
596 KB |
Execution killed with signal 6 |
| 39 |
Runtime error |
77 ms |
512 KB |
Execution killed with signal 6 |
| 40 |
Runtime error |
26 ms |
492 KB |
Execution killed with signal 6 |
