#include "monster.h"
//#include "grader.cpp"
#include<bits/stdc++.h>
using namespace std;
std::vector<int> Solve(int N) {
vector<int> res(N);
function<vector<int>(int,int)> dnc = [&](int l,int r){
if(l==r-1){
vector<int> res={l};
return res;
}
int mid=(l+r)>>1;
vector<int> lt=dnc(l,mid),rt=dnc(mid,r);
vector<int> cc;
for(int i=0,j=0;i+j<r-l;){
if(i<mid-l && (j==r-mid || Query(rt[j],lt[i]))) cc.push_back(lt[i++]);
else cc.push_back(rt[j++]);
}
return cc;
};
vector<int> a=dnc(0,N);
int k=min(N,12);
vector<int> cnt(k,0);
for(int i=0;i<k;i++) for(int j=i+1;j<k;j++){
if(Query(a[i],a[j])) cnt[i]++;
else cnt[j]++;
}
int p=-1;
for(int i=0;i<k;i++) if(cnt[i]==1){
if(p==-1 || Query(a[i],a[p])) p=i;
}
int pre=0;
while(p<N){
for(int i=pre;i<=p;i++) res[a[i]]=pre+p-i;
int c=++p;
while(p<N && Query(a[p],a[pre])) p++;
pre=c;
}
return res;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| 4 |
Correct |
1 ms |
344 KB |
Output is correct |
| 5 |
Correct |
0 ms |
344 KB |
Output is correct |
| 6 |
Correct |
0 ms |
344 KB |
Output is correct |
| 7 |
Correct |
1 ms |
344 KB |
Output is correct |
| 8 |
Correct |
0 ms |
344 KB |
Output is correct |
| 9 |
Correct |
0 ms |
344 KB |
Output is correct |
| 10 |
Correct |
1 ms |
344 KB |
Output is correct |
| 11 |
Correct |
1 ms |
344 KB |
Output is correct |
| 12 |
Correct |
1 ms |
344 KB |
Output is correct |
| 13 |
Correct |
1 ms |
344 KB |
Output is correct |
| 14 |
Correct |
1 ms |
344 KB |
Output is correct |
| 15 |
Correct |
1 ms |
344 KB |
Output is correct |
| 16 |
Correct |
6 ms |
600 KB |
Output is correct |
| 17 |
Correct |
6 ms |
600 KB |
Output is correct |
| 18 |
Correct |
7 ms |
344 KB |
Output is correct |
| 19 |
Correct |
8 ms |
600 KB |
Output is correct |
| 20 |
Correct |
6 ms |
344 KB |
Output is correct |
| 21 |
Correct |
1 ms |
344 KB |
Output is correct |
| 22 |
Correct |
1 ms |
344 KB |
Output is correct |
| 23 |
Correct |
1 ms |
344 KB |
Output is correct |
| 24 |
Correct |
1 ms |
344 KB |
Output is correct |
| 25 |
Correct |
0 ms |
344 KB |
Output is correct |
| 26 |
Correct |
5 ms |
600 KB |
Output is correct |
| 27 |
Correct |
1 ms |
344 KB |
Output is correct |
| 28 |
Correct |
1 ms |
344 KB |
Output is correct |
| 29 |
Correct |
0 ms |
344 KB |
Output is correct |
| 30 |
Correct |
1 ms |
344 KB |
Output is correct |
| 31 |
Correct |
1 ms |
344 KB |
Output is correct |
| 32 |
Correct |
5 ms |
600 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| 4 |
Correct |
1 ms |
344 KB |
Output is correct |
| 5 |
Correct |
0 ms |
344 KB |
Output is correct |
| 6 |
Correct |
0 ms |
344 KB |
Output is correct |
| 7 |
Correct |
1 ms |
344 KB |
Output is correct |
| 8 |
Correct |
0 ms |
344 KB |
Output is correct |
| 9 |
Correct |
0 ms |
344 KB |
Output is correct |
| 10 |
Correct |
1 ms |
344 KB |
Output is correct |
| 11 |
Correct |
1 ms |
344 KB |
Output is correct |
| 12 |
Correct |
1 ms |
344 KB |
Output is correct |
| 13 |
Correct |
1 ms |
344 KB |
Output is correct |
| 14 |
Correct |
1 ms |
344 KB |
Output is correct |
| 15 |
Correct |
1 ms |
344 KB |
Output is correct |
| 16 |
Correct |
6 ms |
600 KB |
Output is correct |
| 17 |
Correct |
6 ms |
600 KB |
Output is correct |
| 18 |
Correct |
7 ms |
344 KB |
Output is correct |
| 19 |
Correct |
8 ms |
600 KB |
Output is correct |
| 20 |
Correct |
6 ms |
344 KB |
Output is correct |
| 21 |
Correct |
1 ms |
344 KB |
Output is correct |
| 22 |
Correct |
1 ms |
344 KB |
Output is correct |
| 23 |
Correct |
1 ms |
344 KB |
Output is correct |
| 24 |
Correct |
1 ms |
344 KB |
Output is correct |
| 25 |
Correct |
0 ms |
344 KB |
Output is correct |
| 26 |
Correct |
5 ms |
600 KB |
Output is correct |
| 27 |
Correct |
1 ms |
344 KB |
Output is correct |
| 28 |
Correct |
1 ms |
344 KB |
Output is correct |
| 29 |
Correct |
0 ms |
344 KB |
Output is correct |
| 30 |
Correct |
1 ms |
344 KB |
Output is correct |
| 31 |
Correct |
1 ms |
344 KB |
Output is correct |
| 32 |
Correct |
5 ms |
600 KB |
Output is correct |
| 33 |
Correct |
44 ms |
936 KB |
Output is correct |
| 34 |
Correct |
42 ms |
928 KB |
Output is correct |
| 35 |
Correct |
40 ms |
600 KB |
Output is correct |
| 36 |
Correct |
35 ms |
676 KB |
Output is correct |
| 37 |
Correct |
39 ms |
676 KB |
Output is correct |
| 38 |
Correct |
43 ms |
856 KB |
Output is correct |
| 39 |
Correct |
43 ms |
852 KB |
Output is correct |
| 40 |
Correct |
35 ms |
668 KB |
Output is correct |
| 41 |
Correct |
39 ms |
932 KB |
Output is correct |
| 42 |
Correct |
44 ms |
684 KB |
Output is correct |
| 43 |
Correct |
29 ms |
676 KB |
Output is correct |
| 44 |
Correct |
31 ms |
856 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
41 ms |
604 KB |
Output is correct |
| 2 |
Correct |
46 ms |
676 KB |
Output is correct |
| 3 |
Correct |
40 ms |
600 KB |
Output is correct |
| 4 |
Correct |
33 ms |
852 KB |
Output is correct |
| 5 |
Correct |
41 ms |
688 KB |
Output is correct |
| 6 |
Correct |
32 ms |
600 KB |
Output is correct |
| 7 |
Correct |
32 ms |
688 KB |
Output is correct |
| 8 |
Correct |
45 ms |
680 KB |
Output is correct |
| 9 |
Correct |
41 ms |
856 KB |
Output is correct |
| 10 |
Correct |
42 ms |
848 KB |
Output is correct |
| 11 |
Correct |
43 ms |
600 KB |
Output is correct |
| 12 |
Correct |
43 ms |
596 KB |
Output is correct |
| 13 |
Correct |
43 ms |
672 KB |
Output is correct |
| 14 |
Correct |
39 ms |
680 KB |
Output is correct |
| 15 |
Correct |
26 ms |
852 KB |
Output is correct |
| 16 |
Correct |
24 ms |
604 KB |
Output is correct |
| 17 |
Correct |
44 ms |
936 KB |
Output is correct |
| 18 |
Correct |
25 ms |
688 KB |
Output is correct |
