#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
#define pf printf
vector<int> todo,v;
bool done[260];
int check(int x){ //swap (0,1),(2,3)...(2*x,2*x+1)
for(int i=0;i<=x;++i){
swap(v[todo[2*i]],v[todo[2*i+1]]);
}
int res=query(v);
for(int i=0;i<=x;++i){
swap(v[todo[2*i]],v[todo[2*i+1]]);
}
return res;
}
void solve(int N) {
for(int i=1;i<=N;++i)v.push_back(i);
while(true){
int res=query(v);
if(res==N)return;
if(res==0)break;
random_shuffle(v.begin(),v.end());
}
int pv=0;
while(true){
todo.clear();
for(int i=0;i<N;++i)if(!done[i])todo.push_back(i);
if(todo.size()==0)break;
random_shuffle(todo.begin(),todo.end());
if(check(todo.size()/2-1)==pv)continue;
int lo=0,hi=todo.size()/2-1,mid,res=0,nw=0;
while(lo<=hi){
mid=(lo+hi)/2;
int tmp=check(mid);
if(tmp==N)return;
if(tmp>pv){
res=mid;
nw=tmp;
hi=mid-1;
}
else lo=mid+1;
}
int a=todo[2*res],b=todo[2*res+1];
swap(v[a],v[b]);
if(nw==N)return;
if(nw==pv+2){
done[a]=true;
done[b]=true;
}
else{
int o=0;
for(int i=0;i<N;++i){
if(!done[i]&&i!=a&&i!=b){ o=i;break; }
}
swap(v[a],v[o]);
int tmp=query(v);
if(tmp==N)return;
swap(v[a],v[o]);
if(tmp>=nw)done[b]=true;
else done[a]=true;
}
pv=query(v);
if(pv==N)return;
}
return;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
200 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
200 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
200 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
