#include <bits/stdc++.h>
#include "monster.h"
using namespace std;
#define ll long long
#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
mt19937 rnd(2342334);
bool query(int a, int b) {
return !Query(a, b);
}
vector<int> merge(vector<int> a, vector<int> b) {
vector<int> c;
int i = 0;
int j = 0;
while (i < (int)a.size() && j < (int)b.size()) {
if (query(a[i], b[j])) {
c.push_back(a[i]);
i += 1;
} else {
c.push_back(b[j]);
j += 1;
}
}
while (i < (int)a.size()) {
c.push_back(a[i]);
i += 1;
}
while (j < (int)b.size()) {
c.push_back(b[j]);
j += 1;
}
return c;
}
vector<int> merge_sort(vector<int> a) {
if (a.size() == 1) {
return a;
}
int sz = (int)a.size();
vector<int> x, y;
for (int i = 0; i < sz; i += 1) {
if (i < sz / 2) {
x.push_back(a[i]);
} else {
y.push_back(a[i]);
}
}
x = merge_sort(x);
y = merge_sort(y);
auto z = merge(x, y);
return z;
}
vector<int> sort_aboba(vector<int> a){
vector<int> b = {a[0]};
for(int i = 1; i < (int)a.size(); i += 1){
int l = -1;
int r = (int)b.size();
while(l + 1 < r){
int m = (l + r) / 2;
if(query(b[m], a[i])){
l = m;
} else{
r = m;
}
}
b.insert(b.begin() + r, a[i]);
}
return b;
}
vector<int> Solve(int n) {
vector<int> t(n);
for (int i = 0; i < n; i += 1) {
t[i] = i;
}
shuffle(all(t), rnd);
t = sort_aboba(t);
if (query(t[0], t[n - 1])) {
int x = -1;
for (int i = n - 2; i >= 0; i -= 1) {
if (!query(t[0], t[i])) {
x = i;
break;
}
}
if (x == -1) {
assert(0);
}
if (x == 1) {
assert(0);
}
int fuck = -1;
if (x == 2) {
assert(0);
bool is_1_mx = false;
for (int i = 3; i < n; i += 1) {
if (!query(t[1], t[i])) {
is_1_mx = true;
break;
}
}
if (is_1_mx) {
swap(t[1], t[2]);
fuck = x + 1;
} else {
swap(t[0], t[1]);
fuck = x + 1;
}
} else {
int m = x + 1;
vector<int> q(m - 2);
for (int i = 0; i < m - 2; i += 1) {
q[i] = query(t[i], t[i + 2]);
}
int d = -1;
for (int i = 0; i + 1 < m - 2; i += 1) {
if (q[i] && q[i + 1]) {
d = i + 1;
break;
}
}
if (d == -1) {
if (q[0]) {
d = 0;
} else if (q[m - 3]) {
d = m - 2;
}
}
if (d == -1) {
assert(0);
} else {
reverse(t.begin(), t.begin() + d + 1);
reverse(t.begin() + d + 1, t.begin() + m);
}
fuck = m;
}
while (fuck < n) {
int new_fuck = -1;
for (int i = fuck; i < n; i += 1) {
if (!query(t[fuck - 1], t[i])) {
new_fuck = i + 1;
break;
}
}
if (new_fuck == -1) {
assert(0);
}
reverse(t.begin() + fuck, t.begin() + new_fuck);
fuck = new_fuck;
}
} else {
vector<int> q(n - 2);
for (int i = 0; i < n - 2; i += 1) {
q[i] = query(t[i], t[i + 2]);
}
int d = -1;
for (int i = 0; i + 1 < n - 2; i += 1) {
if (q[i] && q[i + 1]) {
d = i + 1;
break;
}
}
if (d == -1) {
if (q[0]) {
d = 0;
} else if (q[n - 3]) {
d = n - 2;
}
}
if (d == -1) {
reverse(all(t));
} else {
reverse(t.begin(), t.begin() + d + 1);
reverse(t.begin() + d + 1, t.end());
}
}
vector<int> p(n);
for (int i = 0; i < n; i += 1) {
p[t[i]] = i;
}
return p;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
208 KB |
Output is correct |
| 2 |
Correct |
1 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 |
1 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 |
0 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 |
0 ms |
208 KB |
Output is correct |
| 13 |
Correct |
0 ms |
208 KB |
Output is correct |
| 14 |
Runtime error |
1 ms |
428 KB |
Execution killed with signal 6 |
| 15 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
208 KB |
Output is correct |
| 2 |
Correct |
1 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 |
1 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 |
0 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 |
0 ms |
208 KB |
Output is correct |
| 13 |
Correct |
0 ms |
208 KB |
Output is correct |
| 14 |
Runtime error |
1 ms |
428 KB |
Execution killed with signal 6 |
| 15 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
64 ms |
300 KB |
Partially correct |
| 2 |
Partially correct |
66 ms |
208 KB |
Partially correct |
| 3 |
Partially correct |
37 ms |
328 KB |
Partially correct |
| 4 |
Partially correct |
89 ms |
296 KB |
Partially correct |
| 5 |
Partially correct |
65 ms |
296 KB |
Partially correct |
| 6 |
Partially correct |
33 ms |
312 KB |
Partially correct |
| 7 |
Partially correct |
66 ms |
312 KB |
Partially correct |
| 8 |
Runtime error |
76 ms |
432 KB |
Execution killed with signal 6 |
| 9 |
Halted |
0 ms |
0 KB |
- |
