#include<bits/stdc++.h>
#define rep(i,a,b) for(ll i=(ll)a;i<(ll)b;i++)
#define rrep(i,a,b) for(ll i=(ll)b-1;i>=(ll)a;i--)
#define all(x) begin(x),end(x)
using ll=long long;
using namespace std;
using ull=unsigned long long;
template<typename T,typename U>
inline bool chmax(T&a,const U&b){return (a<b)?a=b,true:false;}
template<typename T,typename U>
inline bool chmin(T&a,const U&b){return (a>b)?a=b,true:false;}
#include "monster.h"
map<pair<int,int>,bool>mp;
bool ask(int a,int b){
if(mp.count({a,b}))return mp[{a,b}];
if(mp.count({b,a}))return mp[{b,a}];
return mp[{a,b}]=Query(a,b);
}
void merge(vector<int>&v){
if(v.size()==1)return;
int mid=v.size()/2;
vector<int>l(v.begin(),v.begin()+mid),r(v.begin()+mid,v.end());
merge(l),merge(r);
int i=0,j=0;
rep(k,0,v.size()){
if(i==l.size())v[k]=r[j++];
else if(j==r.size())v[k]=l[i++];
else if(ask(l[i],r[j]))v[k]=r[j++];
else v[k]=l[i++];
}
return;
}
int sol2(const vector<int>&id){
int n=id.size();
vector<int>cnt(n,0);
vector<vector<int>>a(n,vector<int>(n,0));
rep(i,0,n)rep(j,i+1,n){
bool f=ask(id[i],id[j]);
if(f)cnt[i]++;
else cnt[j]++;
a[i][j]=f;
a[j][i]=!f;
}
vector<pair<int,int>>v(n);
rep(i,0,n)v[i]={cnt[i],id[i]};
sort(all(v));
if(ask(v[1].second,v[0].second))swap(v[0],v[1]);
return v[0].second;
}
vector<int>Solve(int n){
vector<int>id(n);
iota(id.begin(),id.end(),0);
merge(id);
vector<int>tmp(id.begin(),id.begin()+min(10,n));
int start=sol2(tmp);
id.erase(find(all(id),start));
id.insert(id.begin(),start);
rep(i,1,n){
int j=i;
while(j<n&&ask(id[j],start))j++;
reverse(id.begin()+i,id.begin()+min(j+1,n));
if(j==n)break;
start=id[j];
i=j;
}
vector<int>ret(n);
rep(i,0,n)ret[id[i]]=i;
return ret;
}
Compilation message
monster.cpp: In function 'void merge(std::vector<int>&)':
monster.cpp:26:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
26 | if(i==l.size())v[k]=r[j++];
| ~^~~~~~~~~~
monster.cpp:27:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
27 | else if(j==r.size())v[k]=l[i++];
| ~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
208 KB |
Wrong Answer [3] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
208 KB |
Wrong Answer [3] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
88 ms |
800 KB |
Wrong Answer [3] |
| 2 |
Halted |
0 ms |
0 KB |
- |
