#include "monster.h"
#include <bits/stdc++.h>
using namespace std;
mt19937 rnd(228);
vector<int> Solve(int n) {
vector<int> ord(n);
iota(ord.begin(), ord.end(), 0);
shuffle(ord.begin(), ord.end(), rnd);
auto merge_sort = [&](auto self, vector<int> a) -> vector<int> {
if (a.size() == 1) {
return a;
}
int mid = a.size() / 2;
auto L = self(self, vector(a.begin(), a.begin() + mid));
auto R = self(self, vector(a.begin() + mid, a.end()));
a.clear();
int i = 0, j = 0;
while (i < L.size() || j < R.size()) {
if (i < L.size() && (j == R.size() || !Query(L[i], R[j]))) {
a.push_back(L[i++]);
} else {
a.push_back(R[j++]);
}
}
return a;
};
ord = merge_sort(merge_sort, ord);
stable_sort(ord.begin(), ord.end(), [&](int i, int j) {
return !Query(i, j);
});
int k = min(n, 10);
vector<int> win(k);
for (int i = 0; i < k; ++i) {
for (int j = i + 1; j < k; ++j) {
if (Query(ord[i], ord[j])) {
win[i] += 1;
} else {
win[j] += 1;
}
}
}
int fi = min_element(win.begin(), win.end()) - win.begin();
assert(win.begin() + fi != win.end());
int se = min_element(win.begin() + fi + 1, win.end()) - win.begin();
int x = Query(ord[fi], ord[se]) ? fi : se;
rotate(ord.begin(), ord.begin() + x, ord.begin() + x + 1);
x = 0;
for (int i = 1, j = 1; i < n; i = j) {
while (Query(ord[j], ord[x])) {
j += 1;
}
j += 1;
reverse(ord.begin() + i, ord.begin() + j);
x = j - 1;
}
vector<int> ans(n);
for (int i = 0; i < n; ++i) {
ans[ord[i]] = i;
}
return ans;
}
Compilation message
monster.cpp: In instantiation of 'Solve(int)::<lambda(auto:23, std::vector<int>)> [with auto:23 = Solve(int)::<lambda(auto:23, std::vector<int>)>]':
monster.cpp:33:37: required from here
monster.cpp:23:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
23 | while (i < L.size() || j < R.size()) {
| ~~^~~~~~~~~~
monster.cpp:23:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
23 | while (i < L.size() || j < R.size()) {
| ~~^~~~~~~~~~
monster.cpp:24:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
24 | if (i < L.size() && (j == R.size() || !Query(L[i], R[j]))) {
| ~~^~~~~~~~~~
monster.cpp:24:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
24 | if (i < L.size() && (j == R.size() || !Query(L[i], R[j]))) {
| ~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
208 KB |
Output is correct |
| 2 |
Correct |
0 ms |
208 KB |
Output is correct |
| 3 |
Correct |
0 ms |
208 KB |
Output is correct |
| 4 |
Correct |
0 ms |
208 KB |
Output is correct |
| 5 |
Correct |
0 ms |
208 KB |
Output is correct |
| 6 |
Correct |
1 ms |
208 KB |
Output is correct |
| 7 |
Correct |
1 ms |
208 KB |
Output is correct |
| 8 |
Correct |
1 ms |
208 KB |
Output is correct |
| 9 |
Correct |
1 ms |
208 KB |
Output is correct |
| 10 |
Correct |
1 ms |
208 KB |
Output is correct |
| 11 |
Correct |
1 ms |
208 KB |
Output is correct |
| 12 |
Correct |
1 ms |
208 KB |
Output is correct |
| 13 |
Correct |
1 ms |
208 KB |
Output is correct |
| 14 |
Correct |
1 ms |
208 KB |
Output is correct |
| 15 |
Correct |
1 ms |
208 KB |
Output is correct |
| 16 |
Correct |
14 ms |
208 KB |
Output is correct |
| 17 |
Correct |
22 ms |
208 KB |
Output is correct |
| 18 |
Correct |
29 ms |
208 KB |
Output is correct |
| 19 |
Correct |
17 ms |
208 KB |
Output is correct |
| 20 |
Correct |
25 ms |
208 KB |
Output is correct |
| 21 |
Correct |
1 ms |
208 KB |
Output is correct |
| 22 |
Correct |
1 ms |
208 KB |
Output is correct |
| 23 |
Correct |
1 ms |
208 KB |
Output is correct |
| 24 |
Correct |
1 ms |
208 KB |
Output is correct |
| 25 |
Correct |
1 ms |
208 KB |
Output is correct |
| 26 |
Correct |
18 ms |
208 KB |
Output is correct |
| 27 |
Correct |
0 ms |
208 KB |
Output is correct |
| 28 |
Correct |
1 ms |
208 KB |
Output is correct |
| 29 |
Correct |
1 ms |
208 KB |
Output is correct |
| 30 |
Correct |
1 ms |
208 KB |
Output is correct |
| 31 |
Correct |
1 ms |
208 KB |
Output is correct |
| 32 |
Correct |
23 ms |
208 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
208 KB |
Output is correct |
| 2 |
Correct |
0 ms |
208 KB |
Output is correct |
| 3 |
Correct |
0 ms |
208 KB |
Output is correct |
| 4 |
Correct |
0 ms |
208 KB |
Output is correct |
| 5 |
Correct |
0 ms |
208 KB |
Output is correct |
| 6 |
Correct |
1 ms |
208 KB |
Output is correct |
| 7 |
Correct |
1 ms |
208 KB |
Output is correct |
| 8 |
Correct |
1 ms |
208 KB |
Output is correct |
| 9 |
Correct |
1 ms |
208 KB |
Output is correct |
| 10 |
Correct |
1 ms |
208 KB |
Output is correct |
| 11 |
Correct |
1 ms |
208 KB |
Output is correct |
| 12 |
Correct |
1 ms |
208 KB |
Output is correct |
| 13 |
Correct |
1 ms |
208 KB |
Output is correct |
| 14 |
Correct |
1 ms |
208 KB |
Output is correct |
| 15 |
Correct |
1 ms |
208 KB |
Output is correct |
| 16 |
Correct |
14 ms |
208 KB |
Output is correct |
| 17 |
Correct |
22 ms |
208 KB |
Output is correct |
| 18 |
Correct |
29 ms |
208 KB |
Output is correct |
| 19 |
Correct |
17 ms |
208 KB |
Output is correct |
| 20 |
Correct |
25 ms |
208 KB |
Output is correct |
| 21 |
Correct |
1 ms |
208 KB |
Output is correct |
| 22 |
Correct |
1 ms |
208 KB |
Output is correct |
| 23 |
Correct |
1 ms |
208 KB |
Output is correct |
| 24 |
Correct |
1 ms |
208 KB |
Output is correct |
| 25 |
Correct |
1 ms |
208 KB |
Output is correct |
| 26 |
Correct |
18 ms |
208 KB |
Output is correct |
| 27 |
Correct |
0 ms |
208 KB |
Output is correct |
| 28 |
Correct |
1 ms |
208 KB |
Output is correct |
| 29 |
Correct |
1 ms |
208 KB |
Output is correct |
| 30 |
Correct |
1 ms |
208 KB |
Output is correct |
| 31 |
Correct |
1 ms |
208 KB |
Output is correct |
| 32 |
Correct |
23 ms |
208 KB |
Output is correct |
| 33 |
Correct |
128 ms |
296 KB |
Output is correct |
| 34 |
Correct |
171 ms |
208 KB |
Output is correct |
| 35 |
Correct |
137 ms |
328 KB |
Output is correct |
| 36 |
Correct |
126 ms |
296 KB |
Output is correct |
| 37 |
Correct |
116 ms |
208 KB |
Output is correct |
| 38 |
Correct |
142 ms |
292 KB |
Output is correct |
| 39 |
Correct |
118 ms |
296 KB |
Output is correct |
| 40 |
Correct |
90 ms |
208 KB |
Output is correct |
| 41 |
Correct |
118 ms |
300 KB |
Output is correct |
| 42 |
Correct |
105 ms |
300 KB |
Output is correct |
| 43 |
Correct |
110 ms |
296 KB |
Output is correct |
| 44 |
Correct |
131 ms |
208 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
118 ms |
208 KB |
Partially correct |
| 2 |
Partially correct |
103 ms |
336 KB |
Partially correct |
| 3 |
Partially correct |
127 ms |
308 KB |
Partially correct |
| 4 |
Partially correct |
141 ms |
292 KB |
Partially correct |
| 5 |
Partially correct |
117 ms |
208 KB |
Partially correct |
| 6 |
Partially correct |
124 ms |
296 KB |
Partially correct |
| 7 |
Partially correct |
99 ms |
208 KB |
Partially correct |
| 8 |
Partially correct |
131 ms |
208 KB |
Partially correct |
| 9 |
Partially correct |
124 ms |
208 KB |
Partially correct |
| 10 |
Partially correct |
122 ms |
300 KB |
Partially correct |
| 11 |
Partially correct |
149 ms |
208 KB |
Partially correct |
| 12 |
Partially correct |
154 ms |
296 KB |
Partially correct |
| 13 |
Partially correct |
111 ms |
208 KB |
Partially correct |
| 14 |
Partially correct |
122 ms |
208 KB |
Partially correct |
| 15 |
Partially correct |
87 ms |
292 KB |
Partially correct |
| 16 |
Partially correct |
108 ms |
208 KB |
Partially correct |
| 17 |
Partially correct |
115 ms |
292 KB |
Partially correct |
| 18 |
Partially correct |
96 ms |
300 KB |
Partially correct |
