| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 639938 |
2022-09-12T18:12:50 Z |
piOOE |
Scales (IOI15_scales) |
C++17 |
|
517 ms |
7888 KB |
#include <bits/stdc++.h>
#include "scales.h"
using namespace std;
constexpr 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[i] > p[k]) {
swap(i, k);
}
if (p[j] > p[k]) {
swap(j, k);
}
}
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 lightest(vector<int> &p, int i, int j, int k) {
sort(p, i, j, k);
return i;
}
int next(vector<int> &p, int i, int j, int k, int l) {
sort(p, i, j, k);
if (p[l] < p[i] || p[l] > p[k]) {
return i;
} else if (p[l] < p[j]) {
return j;
} else {
return k;
}
}
bool solve(vector<int> mask, int remain) {
if (mask.size() <= 1) {
return true;
} else if (mask.size() > P[remain]) {
return false;
} else if (compare.count(mask)) {
return true;
}
vector<int> one, two, three;
for (int i = 0; i < N - 2; ++i) {
for (int j = i + 1; j < N - 1; ++j) {
for (int k = j + 1; k < N; ++k) {
one.clear(), two.clear(), three.clear();
for (int p: mask) {
int x = lightest(inv[p], i, j, k);
(x == i ? one : (x == j ? two : three)).push_back(p);
}
if (solve(one, remain - 1) && solve(two, remain - 1) && solve(three, remain - 1)) {
compare[mask] = {i, j, k, -3};
return true;
}
one.clear(), two.clear(), three.clear();
for (int p: mask) {
int x = heaviest(inv[p], i, j, k);
(x == i ? one : (x == j ? two : three)).push_back(p);
}
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 (int p: mask) {
int x = median(inv[p], i, j, k);
(x == i ? one : (x == j ? two : three)).push_back(p);
}
if (solve(one, remain - 1) && solve(two, remain - 1) && solve(three, remain - 1)) {
compare[mask] = {i, j, k, -2};
return true;
}
for (int l = 0; l < N; ++l) {
if (i != l && j != l && k != l) {
one.clear(), two.clear(), three.clear();
for (int p: mask) {
int x = next(inv[p], i, j, k, l);
(x == i ? one : (x == j ? two : three)).push_back(p);
}
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> p(N);
iota(p.begin(), p.end(), 0);
for (int i = 0; i < M; ++i) {
inv[i].resize(N);
for (int k = 0; k < N; ++k) {
inv[i][p[k]] = k;
}
perm[i] = p;
next_permutation(p.begin(), p.end());
}
vector<int> mask(M);
iota(mask.begin(), mask.end(), 0);
solve(mask, N);
}
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;
int y;
if (l == -1) {
y = getHeaviest(i + 1, j + 1, k + 1) - 1;
for (int p: mask) {
if (y == heaviest(inv[p], i, j, k)) {
new_mask.push_back(p);
}
}
} else if (l == -2) {
y = getMedian(i + 1, j + 1, k + 1) - 1;
for (int p: mask) {
if (y == median(inv[p], i, j, k)) {
new_mask.push_back(p);
}
}
} else if (l == -3) {
y = getLightest(i + 1, j + 1, k + 1) - 1;
for (int p: mask) {
if (y == lightest(inv[p], i, j, k)) {
new_mask.push_back(p);
}
}
} else {
y = getNextLightest(i + 1, j + 1, k + 1, l + 1) - 1;
for (int p: mask) {
if (y == next(inv[p], i, j, k, l)) {
new_mask.push_back(p);
}
}
}
swap(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 'bool solve(std::vector<int>, int)':
scales.cpp:53:28: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'const int' [-Wsign-compare]
53 | } else if (mask.size() > P[remain]) {
| ~~~~~~~~~~~~^~~~~~~~~~~
scales.cpp: In function 'void init(int)':
scales.cpp:114:15: warning: unused parameter 'T' [-Wunused-parameter]
114 | void init(int T) {
| ~~~~^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
442 ms |
7676 KB |
Output is correct |
| 2 |
Correct |
517 ms |
7752 KB |
Output is correct |
| 3 |
Correct |
465 ms |
7752 KB |
Output is correct |
| 4 |
Correct |
440 ms |
7660 KB |
Output is correct |
| 5 |
Correct |
439 ms |
7676 KB |
Output is correct |
| 6 |
Correct |
450 ms |
7652 KB |
Output is correct |
| 7 |
Correct |
470 ms |
7844 KB |
Output is correct |
| 8 |
Correct |
442 ms |
7656 KB |
Output is correct |
| 9 |
Correct |
442 ms |
7740 KB |
Output is correct |
| 10 |
Correct |
438 ms |
7748 KB |
Output is correct |
| 11 |
Correct |
434 ms |
7628 KB |
Output is correct |
| 12 |
Correct |
454 ms |
7772 KB |
Output is correct |
| 13 |
Correct |
436 ms |
7636 KB |
Output is correct |
| 14 |
Correct |
447 ms |
7644 KB |
Output is correct |
| 15 |
Correct |
439 ms |
7752 KB |
Output is correct |
| 16 |
Correct |
439 ms |
7632 KB |
Output is correct |
| 17 |
Correct |
438 ms |
7868 KB |
Output is correct |
| 18 |
Correct |
436 ms |
7640 KB |
Output is correct |
| 19 |
Correct |
451 ms |
7792 KB |
Output is correct |
| 20 |
Correct |
445 ms |
7700 KB |
Output is correct |
| 21 |
Correct |
445 ms |
7688 KB |
Output is correct |
| 22 |
Correct |
439 ms |
7744 KB |
Output is correct |
| 23 |
Correct |
440 ms |
7888 KB |
Output is correct |
| 24 |
Correct |
461 ms |
7628 KB |
Output is correct |
| 25 |
Correct |
454 ms |
7628 KB |
Output is correct |
| 26 |
Correct |
440 ms |
7660 KB |
Output is correct |
| 27 |
Correct |
452 ms |
7636 KB |
Output is correct |
| 28 |
Correct |
446 ms |
7676 KB |
Output is correct |
| 29 |
Correct |
438 ms |
7628 KB |
Output is correct |
| 30 |
Correct |
452 ms |
7712 KB |
Output is correct |
| 31 |
Correct |
437 ms |
7704 KB |
Output is correct |
| 32 |
Correct |
441 ms |
7684 KB |
Output is correct |
| 33 |
Correct |
448 ms |
7720 KB |
Output is correct |
| 34 |
Correct |
442 ms |
7808 KB |
Output is correct |
| 35 |
Correct |
440 ms |
7708 KB |
Output is correct |
| 36 |
Correct |
447 ms |
7724 KB |
Output is correct |
| 37 |
Correct |
446 ms |
7700 KB |
Output is correct |
| 38 |
Correct |
432 ms |
7740 KB |
Output is correct |
| 39 |
Correct |
435 ms |
7844 KB |
Output is correct |
| 40 |
Correct |
438 ms |
7628 KB |
Output is correct |
