#include <bits/stdc++.h>
#include "monster.h"
#ifndef EVAL
#include "grader.cpp"
#endif
using namespace std;
bool qq(int a, int b) {
return Query(a, b);
}
vector<int> Solve(int n) {
function<vector<int>(int, int)> merge = [&](int l, int r){
if(l == r) return vector<int>{l};
int m = (l + r) >> 1;
vector<int> lx = merge(l, m), rx = merge(m+1, r), res;
l = 0, r = 0;
while(l < (int)lx.size() || r < (int)rx.size()){
if(l < (int)lx.size() && r < (int)rx.size()){
//~ cout<<rx[r]<<" "<<lx[l]<<"\n";
if(qq(lx[l], rx[r])) res.push_back(rx[r++]);
else res.push_back(lx[l++]);
} else if(l < (int)lx.size()){
res.push_back(lx[l++]);
} else {
res.push_back(rx[r++]);
}
}
return res;
};
vector<int> a = merge(0, n - 1);
//~ for(int i=0;i<n;i++) cout<<a[i]<<" ";
//~ cout<<"\n";
int k = min(11, n);
vector<int> in(k);
for(int i=0;i<k;i++){
for(int j=i+1;j<k;j++){
if(qq(a[i], a[j])) in[i]++;
else in[j]++;
}
}
vector<int> tt;
int mn = 1e9;
for(int i=0;i<k;i++){
if(in[i] < mn) mn = in[i], tt = {i};
else if(in[i] == mn) tt.push_back(i);
}
int pos = tt[0];
if((int)tt.size() > 1 && qq(a[tt[1]], a[tt[0]])){
pos = tt[1];
}
vector<int> res;
for(int i=pos;~i;i--){
res.push_back(a[i]);
}
int last = 0, l = pos + 1;
while(l < n){
int r = l;
while(r < n && qq(a[r], a[last])) r++;
for(int i=r;i>=l;i--) res.push_back(a[i]);
last = l, l = r + 1;
}
//~ for(int i=0;i<n;i++) cout<<res[i]<<" ";
//~ cout<<"\n";
vector<int> inv(n);
for(int i=0;i<n;i++) inv[res[i]] = i;
return inv;
}
/*
5
3 1 4 2 0
*/
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
200 KB |
Output is correct |
2 |
Correct |
1 ms |
200 KB |
Output is correct |
3 |
Correct |
1 ms |
200 KB |
Output is correct |
4 |
Correct |
1 ms |
200 KB |
Output is correct |
5 |
Correct |
1 ms |
200 KB |
Output is correct |
6 |
Correct |
1 ms |
200 KB |
Output is correct |
7 |
Correct |
1 ms |
200 KB |
Output is correct |
8 |
Correct |
1 ms |
200 KB |
Output is correct |
9 |
Correct |
1 ms |
200 KB |
Output is correct |
10 |
Correct |
1 ms |
200 KB |
Output is correct |
11 |
Correct |
1 ms |
200 KB |
Output is correct |
12 |
Correct |
1 ms |
200 KB |
Output is correct |
13 |
Correct |
1 ms |
200 KB |
Output is correct |
14 |
Correct |
2 ms |
200 KB |
Output is correct |
15 |
Correct |
1 ms |
200 KB |
Output is correct |
16 |
Correct |
17 ms |
288 KB |
Output is correct |
17 |
Correct |
11 ms |
200 KB |
Output is correct |
18 |
Correct |
13 ms |
288 KB |
Output is correct |
19 |
Correct |
15 ms |
288 KB |
Output is correct |
20 |
Correct |
15 ms |
288 KB |
Output is correct |
21 |
Correct |
1 ms |
200 KB |
Output is correct |
22 |
Correct |
0 ms |
200 KB |
Output is correct |
23 |
Correct |
1 ms |
200 KB |
Output is correct |
24 |
Correct |
1 ms |
200 KB |
Output is correct |
25 |
Correct |
1 ms |
200 KB |
Output is correct |
26 |
Correct |
10 ms |
292 KB |
Output is correct |
27 |
Correct |
0 ms |
200 KB |
Output is correct |
28 |
Correct |
1 ms |
200 KB |
Output is correct |
29 |
Correct |
1 ms |
200 KB |
Output is correct |
30 |
Correct |
1 ms |
200 KB |
Output is correct |
31 |
Correct |
1 ms |
200 KB |
Output is correct |
32 |
Correct |
8 ms |
200 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
200 KB |
Output is correct |
2 |
Correct |
1 ms |
200 KB |
Output is correct |
3 |
Correct |
1 ms |
200 KB |
Output is correct |
4 |
Correct |
1 ms |
200 KB |
Output is correct |
5 |
Correct |
1 ms |
200 KB |
Output is correct |
6 |
Correct |
1 ms |
200 KB |
Output is correct |
7 |
Correct |
1 ms |
200 KB |
Output is correct |
8 |
Correct |
1 ms |
200 KB |
Output is correct |
9 |
Correct |
1 ms |
200 KB |
Output is correct |
10 |
Correct |
1 ms |
200 KB |
Output is correct |
11 |
Correct |
1 ms |
200 KB |
Output is correct |
12 |
Correct |
1 ms |
200 KB |
Output is correct |
13 |
Correct |
1 ms |
200 KB |
Output is correct |
14 |
Correct |
2 ms |
200 KB |
Output is correct |
15 |
Correct |
1 ms |
200 KB |
Output is correct |
16 |
Correct |
17 ms |
288 KB |
Output is correct |
17 |
Correct |
11 ms |
200 KB |
Output is correct |
18 |
Correct |
13 ms |
288 KB |
Output is correct |
19 |
Correct |
15 ms |
288 KB |
Output is correct |
20 |
Correct |
15 ms |
288 KB |
Output is correct |
21 |
Correct |
1 ms |
200 KB |
Output is correct |
22 |
Correct |
0 ms |
200 KB |
Output is correct |
23 |
Correct |
1 ms |
200 KB |
Output is correct |
24 |
Correct |
1 ms |
200 KB |
Output is correct |
25 |
Correct |
1 ms |
200 KB |
Output is correct |
26 |
Correct |
10 ms |
292 KB |
Output is correct |
27 |
Correct |
0 ms |
200 KB |
Output is correct |
28 |
Correct |
1 ms |
200 KB |
Output is correct |
29 |
Correct |
1 ms |
200 KB |
Output is correct |
30 |
Correct |
1 ms |
200 KB |
Output is correct |
31 |
Correct |
1 ms |
200 KB |
Output is correct |
32 |
Correct |
8 ms |
200 KB |
Output is correct |
33 |
Correct |
103 ms |
292 KB |
Output is correct |
34 |
Correct |
74 ms |
284 KB |
Output is correct |
35 |
Correct |
86 ms |
408 KB |
Output is correct |
36 |
Correct |
104 ms |
280 KB |
Output is correct |
37 |
Correct |
91 ms |
276 KB |
Output is correct |
38 |
Correct |
81 ms |
536 KB |
Output is correct |
39 |
Correct |
45 ms |
288 KB |
Output is correct |
40 |
Correct |
84 ms |
284 KB |
Output is correct |
41 |
Correct |
99 ms |
296 KB |
Output is correct |
42 |
Correct |
73 ms |
292 KB |
Output is correct |
43 |
Correct |
55 ms |
296 KB |
Output is correct |
44 |
Correct |
53 ms |
280 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
50 ms |
276 KB |
Output is correct |
2 |
Correct |
81 ms |
272 KB |
Output is correct |
3 |
Correct |
73 ms |
292 KB |
Output is correct |
4 |
Correct |
69 ms |
280 KB |
Output is correct |
5 |
Correct |
69 ms |
280 KB |
Output is correct |
6 |
Correct |
38 ms |
280 KB |
Output is correct |
7 |
Correct |
86 ms |
292 KB |
Output is correct |
8 |
Correct |
99 ms |
288 KB |
Output is correct |
9 |
Correct |
61 ms |
292 KB |
Output is correct |
10 |
Correct |
98 ms |
288 KB |
Output is correct |
11 |
Correct |
86 ms |
200 KB |
Output is correct |
12 |
Correct |
53 ms |
288 KB |
Output is correct |
13 |
Correct |
86 ms |
200 KB |
Output is correct |
14 |
Correct |
82 ms |
276 KB |
Output is correct |
15 |
Correct |
44 ms |
292 KB |
Output is correct |
16 |
Correct |
51 ms |
280 KB |
Output is correct |
17 |
Correct |
82 ms |
288 KB |
Output is correct |
18 |
Correct |
43 ms |
200 KB |
Output is correct |