#include<bits/stdc++.h>
#include "monster.h"
//#include"grader.cpp"
using namespace std;
mt19937 mt(time(NULL));
vector<int>brute_force(vector<int>v){
int n=v.size();
vector<vector<bool>>res(n,vector<bool>(n,0));
for(int i=0;i<n;i++)
for(int j=i+1;j<n;j++)
res[j][i]=!(res[i][j]=Query(v[i],v[j]));
vector<pair<int,int>>cnt(n);
for (int i=0;i<n;i++)
cnt[i]={count(res[i].begin(),res[i].end(),1),v[i]};
sort(cnt.begin(),cnt.end());
for(int i=0;i<n;i++)v[i]=cnt[i].second;
if(Query(v[1],v[0]))swap(v[0],v[1]);
if(Query(v[n-1],v[n-2]))swap(v[n-2],v[n-1]);
return v;
}
vector<int>merge_sort(vector<int>v){
if(v.size()==1)return v;
shuffle(v.begin(),v.end(),mt);
int m=v.size()/2;
vector<int>l(v.begin(),v.begin()+m),r(v.begin()+m,v.end());
l=merge_sort(l);
r=merge_sort(r);
int i=0,j=0;
for(int k=0;k<v.size();k++) {
if(i==l.size())v[k]=r[j++];
else if(j==r.size())v[k]=l[i++];
else if(Query(l[i],r[j]))v[k]=r[j++];
else v[k]=l[i++];
}
return v;
}
vector<int>Solve(int N){
vector<int>res(N);
iota(res.begin(),res.end(),0);
res=merge_sort(res);
vector<int>s(res.begin(),res.begin()+min(13,N));
s=brute_force(s);
int zero=s[0];
res.erase(find(res.begin(),res.end(),zero));
res.insert(res.begin(),zero);
for(int i=1;i<N;i++){
int j=i;
while(j<N&&Query(res[j],zero))j++;
reverse(res.begin()+i,res.begin()+min(j + 1, N));
zero=res[j];
i=j;
}
vector<int>ans(N);
for(int i=0;i<N;i++)ans[res[i]]=i;
return ans;
}
Compilation message
monster.cpp: In function 'std::vector<int> merge_sort(std::vector<int>)':
monster.cpp:29:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
29 | for(int k=0;k<v.size();k++) {
| ~^~~~~~~~~
monster.cpp:30:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
30 | if(i==l.size())v[k]=r[j++];
| ~^~~~~~~~~~
monster.cpp:31:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
31 | else if(j==r.size())v[k]=l[i++];
| ~^~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
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 |
1 ms |
208 KB |
Output is correct |
6 |
Correct |
1 ms |
256 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 |
13 ms |
208 KB |
Output is correct |
17 |
Correct |
15 ms |
208 KB |
Output is correct |
18 |
Correct |
13 ms |
208 KB |
Output is correct |
19 |
Correct |
13 ms |
208 KB |
Output is correct |
20 |
Correct |
16 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 |
15 ms |
208 KB |
Output is correct |
27 |
Correct |
0 ms |
208 KB |
Output is correct |
28 |
Correct |
0 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 |
228 KB |
Output is correct |
32 |
Correct |
7 ms |
208 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
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 |
1 ms |
208 KB |
Output is correct |
6 |
Correct |
1 ms |
256 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 |
13 ms |
208 KB |
Output is correct |
17 |
Correct |
15 ms |
208 KB |
Output is correct |
18 |
Correct |
13 ms |
208 KB |
Output is correct |
19 |
Correct |
13 ms |
208 KB |
Output is correct |
20 |
Correct |
16 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 |
15 ms |
208 KB |
Output is correct |
27 |
Correct |
0 ms |
208 KB |
Output is correct |
28 |
Correct |
0 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 |
228 KB |
Output is correct |
32 |
Correct |
7 ms |
208 KB |
Output is correct |
33 |
Correct |
92 ms |
208 KB |
Output is correct |
34 |
Correct |
79 ms |
212 KB |
Output is correct |
35 |
Correct |
76 ms |
300 KB |
Output is correct |
36 |
Correct |
69 ms |
208 KB |
Output is correct |
37 |
Correct |
87 ms |
208 KB |
Output is correct |
38 |
Correct |
69 ms |
208 KB |
Output is correct |
39 |
Correct |
93 ms |
208 KB |
Output is correct |
40 |
Correct |
98 ms |
208 KB |
Output is correct |
41 |
Correct |
90 ms |
208 KB |
Output is correct |
42 |
Correct |
72 ms |
208 KB |
Output is correct |
43 |
Correct |
82 ms |
208 KB |
Output is correct |
44 |
Correct |
103 ms |
208 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
62 ms |
208 KB |
Output is correct |
2 |
Correct |
67 ms |
296 KB |
Output is correct |
3 |
Correct |
87 ms |
208 KB |
Output is correct |
4 |
Correct |
121 ms |
228 KB |
Output is correct |
5 |
Correct |
144 ms |
208 KB |
Output is correct |
6 |
Correct |
61 ms |
208 KB |
Output is correct |
7 |
Correct |
64 ms |
300 KB |
Output is correct |
8 |
Correct |
88 ms |
208 KB |
Output is correct |
9 |
Correct |
123 ms |
216 KB |
Output is correct |
10 |
Correct |
83 ms |
208 KB |
Output is correct |
11 |
Correct |
75 ms |
208 KB |
Output is correct |
12 |
Correct |
93 ms |
208 KB |
Output is correct |
13 |
Correct |
96 ms |
208 KB |
Output is correct |
14 |
Correct |
65 ms |
208 KB |
Output is correct |
15 |
Correct |
55 ms |
208 KB |
Output is correct |
16 |
Correct |
57 ms |
208 KB |
Output is correct |
17 |
Correct |
44 ms |
208 KB |
Output is correct |
18 |
Correct |
59 ms |
208 KB |
Output is correct |