#include <bits/stdc++.h>
using namespace std;
#include "scales.h"
const int N = 6, M = 720, P[] = {1, 3, 9, 27, 81, 243, 729};
map<vector<int>, array<int, 4>> compare;
vector<int> perm[M], inv[M];
int ans[N];
void sort(vector<int> &p, int &i, int &j, int &k) {
if (p[i] > p[j]) {
swap(i, j);
}
if (p[j] > p[k]) {
swap(j, k);
}
if (p[i] > p[j]) {
swap(i, j);
}
}
int lightest(vector<int> &p, int i, int j, int k) {
sort(p, i, j, k);
return i;
}
int heaviest(vector<int> &p, int i, int j, int k) {
sort(p, i, j, k);
return k;
}
int median(vector<int> &p, int i, int j, int k) {
sort(p, i, j, k);
return j;
}
int next(vector<int> &p, int i, int j, int k, int l) {
sort(p, i, j, k);
if (p[l] < p[i]) {
return i;
} else if (p[l] < p[j]) {
return j;
} else if (p[l] < p[k]) {
return k;
} else {
return i;
}
}
bool solve(vector<int> mask, int remain) {
if (mask.size() <= 1) {
return true;
} else if ((int) mask.size() > P[remain]) {
return false;
} else if (compare.count(mask) > 0) {
return true;
}
vector<int> one, two, three;
for (int i = 0; i < N; ++i) {
for (int j = i + 1; j < N; ++j) {
for (int k = j + 1; k < N; ++k) {
one.clear(), two.clear(), three.clear();
for (auto u : mask) {
int x = lightest(inv[u], i, j, k);
(x == i ? one : (x == j ? two : three)).push_back(u);
}
if (solve(one, remain - 1) &&
solve(two, remain - 1) &&
solve(three, remain - 1)) {
compare[mask] = {i, j, k, -1};
return true;
}
one.clear(), two.clear(), three.clear();
for (auto u : mask) {
int x = heaviest(inv[u], i, j, k);
(x == i ? one : (x == j ? two : three)).push_back(u);
}
if (solve(one, remain - 1) &&
solve(two, remain - 1) &&
solve(three, remain - 1)) {
compare[mask] = {i, j, k, -2};
return true;
}
one.clear(), two.clear(), three.clear();
for (auto u : mask) {
int x = median(inv[u], i, j, k);
(x == i ? one : (x == j ? two : three)).push_back(u);
}
if (solve(one, remain - 1) &&
solve(two, remain - 1) &&
solve(three, remain - 1)) {
compare[mask] = {i, j, k, -3};
return true;
}
for (int l = 0; l < N; ++l) {
if (l != i && l != j && l != k) {
one.clear(), two.clear(), three.clear();
for (auto u : mask) {
int x = next(inv[u], i, j, k, l);
(x == i ? one : (x == j ? two : three)).push_back(u);
}
if (solve(one, remain - 1) &&
solve(two, remain - 1) &&
solve(three, remain - 1)) {
compare[mask] = {i, j, k, l};
return true;
}
}
}
}
}
}
return false;
}
void init(int t) {
vector<int> temp(N);
iota(temp.begin(), temp.end(), 0);
for (int i = 0; i < M; ++i) {
perm[i] = temp;
inv[i].resize(6);
for (int j = 0; j < N; ++j) {
inv[i][perm[i][j]] = j;
}
next_permutation(temp.begin(), temp.end());
}
vector<int> mask(M);
iota(mask.begin(), mask.end(), 0);
solve(mask, 6);
}
void orderCoins() {
vector<int> mask(M);
iota(mask.begin(), mask.end(), 0);
while (mask.size() > 1) {
auto [i, j, k, l] = compare[mask];
vector<int> new_mask;
if (l == -1) {
int x = getLightest(i + 1, j + 1, k + 1) - 1;
for (auto u : mask) {
if (lightest(inv[u], i, j, k) == x) {
new_mask.push_back(u);
}
}
} else if (l == -2) {
int x = getHeaviest(i + 1, j + 1, k + 1) - 1;
for (auto u : mask) {
if (heaviest(inv[u], i, j, k) == x) {
new_mask.push_back(u);
}
}
} else if (l == -3) {
int x = getMedian(i + 1, j + 1, k + 1) - 1;
for (auto u : mask) {
if (median(inv[u], i, j, k) == x) {
new_mask.push_back(u);
}
}
} else {
int x = getNextLightest(i + 1, j + 1, k + 1, l + 1) - 1;
for (auto u : mask) {
if (next(inv[u], i, j, k, l) == x) {
new_mask.push_back(u);
}
}
}
mask = new_mask;
}
for (int i = 0; i < N; ++i) {
ans[i] = perm[mask[0]][i] + 1;
}
answer(ans);
}
Compilation message
scales.cpp: In function 'void init(int)':
scales.cpp:123:15: warning: unused parameter 't' [-Wunused-parameter]
123 | void init(int t) {
| ~~~~^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
560 ms |
7640 KB |
Output is correct |
| 2 |
Correct |
557 ms |
7692 KB |
Output is correct |
| 3 |
Correct |
603 ms |
7724 KB |
Output is correct |
| 4 |
Correct |
578 ms |
7720 KB |
Output is correct |
| 5 |
Correct |
614 ms |
7736 KB |
Output is correct |
| 6 |
Correct |
611 ms |
7632 KB |
Output is correct |
| 7 |
Correct |
576 ms |
7736 KB |
Output is correct |
| 8 |
Correct |
600 ms |
7668 KB |
Output is correct |
| 9 |
Correct |
587 ms |
7648 KB |
Output is correct |
| 10 |
Correct |
591 ms |
7720 KB |
Output is correct |
| 11 |
Correct |
561 ms |
7664 KB |
Output is correct |
| 12 |
Correct |
611 ms |
7712 KB |
Output is correct |
| 13 |
Correct |
598 ms |
7640 KB |
Output is correct |
| 14 |
Correct |
584 ms |
7736 KB |
Output is correct |
| 15 |
Correct |
655 ms |
7760 KB |
Output is correct |
| 16 |
Correct |
545 ms |
7676 KB |
Output is correct |
| 17 |
Correct |
616 ms |
7632 KB |
Output is correct |
| 18 |
Correct |
628 ms |
7708 KB |
Output is correct |
| 19 |
Correct |
645 ms |
7664 KB |
Output is correct |
| 20 |
Correct |
595 ms |
7716 KB |
Output is correct |
| 21 |
Correct |
595 ms |
7668 KB |
Output is correct |
| 22 |
Correct |
597 ms |
7732 KB |
Output is correct |
| 23 |
Correct |
603 ms |
7648 KB |
Output is correct |
| 24 |
Correct |
562 ms |
7736 KB |
Output is correct |
| 25 |
Correct |
590 ms |
7620 KB |
Output is correct |
| 26 |
Correct |
562 ms |
7824 KB |
Output is correct |
| 27 |
Correct |
595 ms |
7724 KB |
Output is correct |
| 28 |
Correct |
600 ms |
7740 KB |
Output is correct |
| 29 |
Correct |
580 ms |
7680 KB |
Output is correct |
| 30 |
Correct |
612 ms |
7636 KB |
Output is correct |
| 31 |
Correct |
647 ms |
7700 KB |
Output is correct |
| 32 |
Correct |
595 ms |
7664 KB |
Output is correct |
| 33 |
Correct |
559 ms |
7648 KB |
Output is correct |
| 34 |
Correct |
660 ms |
7744 KB |
Output is correct |
| 35 |
Correct |
583 ms |
7688 KB |
Output is correct |
| 36 |
Correct |
609 ms |
7664 KB |
Output is correct |
| 37 |
Correct |
558 ms |
7852 KB |
Output is correct |
| 38 |
Correct |
610 ms |
7648 KB |
Output is correct |
| 39 |
Correct |
613 ms |
7640 KB |
Output is correct |
| 40 |
Correct |
611 ms |
7660 KB |
Output is correct |
