#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> brute_force(std::vector<int>)':
monster.cpp:12:30: error: 'N' was not declared in this scope
12 | vector<pair<int,int>>cnt(N);
| ^
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++];
| ~^~~~~~~~~~
