#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
#define pf printf
vector<int> todo,v;
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());
}
for(int i=0;i<N;++i)todo.push_back(i);
random_shuffle(todo.begin(),todo.end());
int pv=0;
while(!todo.empty()){
if(check(todo.size()/2-1)==pv){
random_shuffle(todo.begin(),todo.end());
continue;
}
int lo=0,hi=todo.size()/2-1,mid,res,val;
while(lo<=hi){
mid=(lo+hi)/2;
int tmp=check(mid);
if(tmp==N)return;
if(tmp>pv){
res=mid;
val=tmp;
hi=mid-1;
}
else lo=mid+1;
}
if(val==pv+2){
swap(v[todo[2*res]],v[todo[2*res+1]]);
todo.erase(todo.begin()+2*res,todo.begin()+2*res+2);
}
else{
swap(v[todo[2*res]],v[todo[2*res+1]]);
int o=(2*res+2<todo.size())?2*res+2:2*res-1;
swap(v[todo[2*res]],v[todo[o]]);
int tmp=query(v);
if(tmp==N)return;
swap(v[todo[2*res]],v[todo[o]]);
if(tmp>pv){
todo.erase(todo.begin()+2*res+1);
}
else todo.erase(todo.begin()+2*res);
}
pv=query(v);
if(pv==N)return;
}
return;
}
Compilation message
mouse.cpp: In function 'void solve(int)':
mouse.cpp:55:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
55 | int o=(2*res+2<todo.size())?2*res+2:2*res-1;
| ~~~~~~~^~~~~~~~~~~~
mouse.cpp:49:3: warning: 'val' may be used uninitialized in this function [-Wmaybe-uninitialized]
49 | if(val==pv+2){
| ^~
mouse.cpp:50:32: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
50 | swap(v[todo[2*res]],v[todo[2*res+1]]);
| ~^~~~
| # |
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 |
- |
