#include "scales.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5;
vector<vector<int>> allPerm;
vector<pair<int, vector<int>>> OP;
int ask[MAXN];
int nxt[MAXN][4];
int done[MAXN];
int timer = 0;
bool init(int cur, int sz, vector<int> index) {
if (index.size() <= 1) {
if (index.size() == 1) {
done[cur] = 1;
ask[cur] = index[0];
}
return 1;
}
for (int z = 0; z < OP.size(); z++) {
int op = OP[z].first;
vector<int> ques = OP[z].second;
bool ok = 1;
vector<int> ans[3];
for (int id : index) {
int a[3], b[6];
for (int i = 0; i < 3; i++) a[i] = allPerm[id][ques[i]];
sort(a, a + 3);
for (int i = 0; i < 3; i++) b[allPerm[id][ques[i]]] = i;
if (op == 0) { // min
ans[b[a[0]]].emplace_back(id);
} else if (op == 1) { // med
ans[b[a[1]]].emplace_back(id);
} else if (op == 2) { // max
ans[b[a[2]]].emplace_back(id);
} else { // spec
if (allPerm[id][ques[3]] < a[0]) {
ans[b[a[0]]].emplace_back(id);
} else if (allPerm[id][ques[3]] < a[1]) {
ans[b[a[1]]].emplace_back(id);
} else if (allPerm[id][ques[3]] < a[2]) {
ans[b[a[2]]].emplace_back(id);
} else {
ans[b[a[0]]].emplace_back(id);
}
}
}
if (ans[0].size() > sz / 3) continue;
if (ans[1].size() > sz / 3) continue;
if (ans[2].size() > sz / 3) continue;
for (int i = 0; i < 3; i++) {
nxt[cur][i] = timer++;
ok &= init(nxt[cur][i], sz / 3, ans[i]);
}
if (ok) return ask[cur] = z, 1;
}
return 0;
}
void init(int T) {
vector<int> a(6);
iota(a.begin(), a.end(), 0);
do {
allPerm.emplace_back(a);
} while (next_permutation(a.begin(), a.end()));
vector<int> index(720);
iota(index.begin(), index.end(), 0);
for (int i = 0; i < 1 << 6;++i) {
if (__builtin_popcount(i) == 3) {
vector<int> ques;
for (int j = 0;j < 6;++j){
if (i >> j & 1) ques.emplace_back(j);
}
for (int j = 0; j < 3; j++) OP.emplace_back(j, ques);
for (int j = 0; j < 6; j++) {
if (i >> j & 1 ^ 1) {
ques.emplace_back(j);
OP.emplace_back(3, ques);
ques.pop_back();
}
}
}
}
assert(init(timer++, 729, index));
}
int F(int cur) {
if (done[cur]) return ask[cur];
int op = OP[ask[cur]].first;
vector<int> ques = OP[ask[cur]].second; int answer = -1;
if(op == 0) { answer = getLightest(ques[0] + 1, ques[1] + 1, ques[2] + 1);}
else if (op == 1) {answer = getMedian(ques[0] + 1, ques[1] + 1, ques[2] + 1);}
else if (op == 2) {answer = getHeaviest(ques[0] + 1, ques[1] + 1, ques[2] + 1);}
else{answer = getNextLightest(ques[0] + 1, ques[1] + 1, ques[2] + 1, ques[3] + 1);}
for(int i = 0;i<3;++i){
if(answer == ques[i] + 1) return F(nxt[cur][i]);
}
return assert(0),-1;
}
void orderCoins() {
int id = F(0), W[6];
for (int i = 0;i < 6;++i) W[allPerm[id][i]] = i + 1;
answer(W);
}
Compilation message
scales.cpp: In function 'bool init(int, int, std::vector<int>)':
scales.cpp:19:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::vector<int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
19 | for (int z = 0; z < OP.size(); z++) {
| ~~^~~~~~~~~~~
scales.cpp:47:35: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
47 | if (ans[0].size() > sz / 3) continue;
| ~~~~~~~~~~~~~~^~~~~~~~
scales.cpp:48:35: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
48 | if (ans[1].size() > sz / 3) continue;
| ~~~~~~~~~~~~~~^~~~~~~~
scales.cpp:49:35: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
49 | if (ans[2].size() > sz / 3) continue;
| ~~~~~~~~~~~~~~^~~~~~~~
scales.cpp: In function 'void init(int)':
scales.cpp:75:44: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
75 | if (i >> j & 1 ^ 1) {
| ~~~~~~~^~~
scales.cpp:59:15: warning: unused parameter 'T' [-Wunused-parameter]
59 | void init(int T) {
| ~~~~^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
72 ms |
392 KB |
Output is correct |
| 2 |
Correct |
69 ms |
396 KB |
Output is correct |
| 3 |
Correct |
66 ms |
392 KB |
Output is correct |
| 4 |
Correct |
67 ms |
384 KB |
Output is correct |
| 5 |
Correct |
66 ms |
400 KB |
Output is correct |
| 6 |
Correct |
69 ms |
388 KB |
Output is correct |
| 7 |
Correct |
71 ms |
384 KB |
Output is correct |
| 8 |
Correct |
74 ms |
392 KB |
Output is correct |
| 9 |
Correct |
65 ms |
388 KB |
Output is correct |
| 10 |
Correct |
68 ms |
392 KB |
Output is correct |
| 11 |
Correct |
63 ms |
400 KB |
Output is correct |
| 12 |
Correct |
64 ms |
384 KB |
Output is correct |
| 13 |
Correct |
64 ms |
392 KB |
Output is correct |
| 14 |
Correct |
63 ms |
416 KB |
Output is correct |
| 15 |
Correct |
66 ms |
632 KB |
Output is correct |
| 16 |
Correct |
67 ms |
396 KB |
Output is correct |
| 17 |
Correct |
69 ms |
340 KB |
Output is correct |
| 18 |
Correct |
63 ms |
384 KB |
Output is correct |
| 19 |
Correct |
63 ms |
404 KB |
Output is correct |
| 20 |
Correct |
65 ms |
512 KB |
Output is correct |
| 21 |
Correct |
65 ms |
304 KB |
Output is correct |
| 22 |
Correct |
66 ms |
396 KB |
Output is correct |
| 23 |
Correct |
70 ms |
396 KB |
Output is correct |
| 24 |
Correct |
66 ms |
396 KB |
Output is correct |
| 25 |
Correct |
68 ms |
392 KB |
Output is correct |
| 26 |
Correct |
64 ms |
380 KB |
Output is correct |
| 27 |
Correct |
67 ms |
400 KB |
Output is correct |
| 28 |
Correct |
71 ms |
392 KB |
Output is correct |
| 29 |
Correct |
74 ms |
404 KB |
Output is correct |
| 30 |
Correct |
70 ms |
388 KB |
Output is correct |
| 31 |
Correct |
69 ms |
404 KB |
Output is correct |
| 32 |
Correct |
67 ms |
460 KB |
Output is correct |
| 33 |
Correct |
67 ms |
408 KB |
Output is correct |
| 34 |
Correct |
70 ms |
392 KB |
Output is correct |
| 35 |
Correct |
69 ms |
384 KB |
Output is correct |
| 36 |
Correct |
68 ms |
384 KB |
Output is correct |
| 37 |
Correct |
66 ms |
396 KB |
Output is correct |
| 38 |
Correct |
66 ms |
392 KB |
Output is correct |
| 39 |
Correct |
69 ms |
396 KB |
Output is correct |
| 40 |
Correct |
73 ms |
400 KB |
Output is correct |
