#include "scales.h"
#include <bits/stdc++.h>
using namespace std;
int getHeaviest(vector<int> W, int A, int B, int C) {
int res = A;
if (W[B - 1] > W[res - 1]) {
res = B;
}
if (W[C - 1] > W[res - 1]) {
res = C;
}
return res;
}
int getLightest(vector<int> W, int A, int B, int C) {
int res = A;
if (W[B - 1] < W[res - 1]) {
res = B;
}
if (W[C - 1] < W[res - 1]) {
res = C;
}
return res;
}
int getMedian(vector<int> W, int A, int B, int C) {
return A + B + C - getLightest(W, A, B, C) - getHeaviest(W, A, B, C);
}
int getNextLightest(vector<int> W, int A, int B, int C, int D) {
int res = -1;
if (W[A - 1] > W[D - 1] && (res == -1 || W[A - 1] < W[res - 1])) {
res = A;
}
if (W[B - 1] > W[D - 1] && (res == -1 || W[B - 1] < W[res - 1])) {
res = B;
}
if (W[C - 1] > W[D - 1] && (res == -1 || W[C - 1] < W[res - 1])) {
res = C;
}
if (res == -1) {
return getLightest(W, A, B, C);
}
else {
return res;
}
}
int Q[120][5];
int W[6];
int solve(vector<vector<int>> cands, int rem) {
if ((int)cands.size() <= 1) {
return 120;
}
int lim = 1;
for (int i = 0; i < rem - 1; i++) {
lim *= 3;
}
for (int id = 0; id < 120; id++) {
int A = Q[id][0];
int B = Q[id][1];
int C = Q[id][2];
int D = Q[id][3];
int type = Q[id][4];
vector<vector<int>> candsA, candsB, candsC;
for (auto cand: cands) {
int res = -1;
if (type == 1) {
res = getHeaviest(cand, A, B, C);
}
if (type == 2) {
res = getLightest(cand, A, B, C);
}
if (type == 3) {
res = getMedian(cand, A, B, C);
}
if (type == 4) {
res = getNextLightest(cand, A, B, C, D);
}
if (res == A) {
candsA.push_back(cand);
}
if (res == B) {
candsB.push_back(cand);
}
if (res == C) {
candsC.push_back(cand);
}
}
if (candsA.empty() + candsB.empty() + candsC.empty() == 2) {
continue;
}
if ((int)candsA.size() > lim || (int)candsB.size() > lim || (int)candsC.size() > lim) {
continue;
}
if (solve(candsA, rem - 1) != -1 && solve(candsB, rem - 1) != 1 && solve(candsC, rem - 1) != -1) {
return id;
}
}
return -1;
}
void init(int T) {
int cnt = 0;
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 type = 1; type <= 3; type++) {
Q[cnt][0] = A;
Q[cnt][1] = B;
Q[cnt][2] = C;
Q[cnt][3] = -1;
Q[cnt][4] = type;
cnt++;
}
}
}
}
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) {
Q[cnt][0] = A;
Q[cnt][1] = B;
Q[cnt][2] = C;
Q[cnt][3] = D;
Q[cnt][4] = 4;
cnt++;
}
}
}
}
}
}
void orderCoins() {
vector<vector<int>> cands;
vector<int> perm(6);
for (int i = 0; i < 6; i++) {
perm[i] = i + 1;
}
do {
cands.push_back(perm);
}
while (next_permutation(perm.begin(), perm.end()));
int rem = 6;
while ((int)cands.size() > 1) {
int id = solve(cands, rem);
int A = Q[id][0];
int B = Q[id][1];
int C = Q[id][2];
int D = Q[id][3];
int type = Q[id][4];
vector<vector<int>> candsA, candsB, candsC;
for (auto cand: cands) {
int res = -1;
if (type == 1) {
res = getHeaviest(cand, A, B, C);
}
if (type == 2) {
res = getLightest(cand, A, B, C);
}
if (type == 3) {
res = getMedian(cand, A, B, C);
}
if (type == 4) {
res = getNextLightest(cand, A, B, C, D);
}
if (res == A) {
candsA.push_back(cand);
}
if (res == B) {
candsB.push_back(cand);
}
if (res == C) {
candsC.push_back(cand);
}
}
int res = -1;
if (type == 1) {
res = getHeaviest(A, B, C);
}
if (type == 2) {
res = getLightest(A, B, C);
}
if (type == 3) {
res = getMedian(A, B, C);
}
if (type == 4) {
res = getNextLightest(A, B, C, D);
}
if (res == A) {
cands.swap(candsA);
}
if (res == B) {
cands.swap(candsB);
}
if (res == C) {
cands.swap(candsC);
}
rem--;
}
perm = cands[0];
for (int i = 0; i < 6; i++) {
W[perm[i] - 1] = i + 1;
}
answer(W);
return;
}
Compilation message
scales.cpp: In function 'void init(int)':
scales.cpp:105:15: warning: unused parameter 'T' [-Wunused-parameter]
105 | void init(int T) {
| ~~~~^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
596 ms |
508 KB |
Output is correct |
| 2 |
Correct |
602 ms |
504 KB |
Output is correct |
| 3 |
Correct |
600 ms |
500 KB |
Output is correct |
| 4 |
Correct |
602 ms |
504 KB |
Output is correct |
| 5 |
Correct |
597 ms |
468 KB |
Output is correct |
| 6 |
Correct |
616 ms |
608 KB |
Output is correct |
| 7 |
Correct |
599 ms |
468 KB |
Output is correct |
| 8 |
Correct |
607 ms |
468 KB |
Output is correct |
| 9 |
Correct |
602 ms |
508 KB |
Output is correct |
| 10 |
Correct |
604 ms |
500 KB |
Output is correct |
| 11 |
Correct |
599 ms |
468 KB |
Output is correct |
| 12 |
Correct |
627 ms |
500 KB |
Output is correct |
| 13 |
Correct |
601 ms |
596 KB |
Output is correct |
| 14 |
Correct |
598 ms |
500 KB |
Output is correct |
| 15 |
Correct |
600 ms |
468 KB |
Output is correct |
| 16 |
Correct |
610 ms |
504 KB |
Output is correct |
| 17 |
Correct |
656 ms |
504 KB |
Output is correct |
| 18 |
Correct |
603 ms |
496 KB |
Output is correct |
| 19 |
Correct |
783 ms |
500 KB |
Output is correct |
| 20 |
Correct |
611 ms |
500 KB |
Output is correct |
| 21 |
Correct |
607 ms |
588 KB |
Output is correct |
| 22 |
Correct |
605 ms |
468 KB |
Output is correct |
| 23 |
Correct |
601 ms |
428 KB |
Output is correct |
| 24 |
Correct |
611 ms |
496 KB |
Output is correct |
| 25 |
Correct |
608 ms |
504 KB |
Output is correct |
| 26 |
Correct |
597 ms |
504 KB |
Output is correct |
| 27 |
Correct |
597 ms |
504 KB |
Output is correct |
| 28 |
Correct |
600 ms |
500 KB |
Output is correct |
| 29 |
Correct |
612 ms |
500 KB |
Output is correct |
| 30 |
Correct |
606 ms |
496 KB |
Output is correct |
| 31 |
Correct |
606 ms |
500 KB |
Output is correct |
| 32 |
Correct |
615 ms |
500 KB |
Output is correct |
| 33 |
Correct |
611 ms |
468 KB |
Output is correct |
| 34 |
Correct |
600 ms |
592 KB |
Output is correct |
| 35 |
Correct |
604 ms |
592 KB |
Output is correct |
| 36 |
Correct |
601 ms |
468 KB |
Output is correct |
| 37 |
Correct |
623 ms |
624 KB |
Output is correct |
| 38 |
Correct |
601 ms |
496 KB |
Output is correct |
| 39 |
Correct |
624 ms |
500 KB |
Output is correct |
| 40 |
Correct |
626 ms |
500 KB |
Output is correct |
