//~ #include "grader.h"
#include <bits/stdc++.h>
using namespace std;
#define ar array
int n, tot;
vector<int> todo, a, B;
//~ int query(vector<int> a){
//~ assert((int)a.size() == n);
//~ int res = 0;
//~ for(int i=0;i<n;i++){
//~ res += (a[i] == B[i]);
//~ } tot++;
//~ if(tot > 2400){
//~ assert(false);
//~ }
//~ if(res == n){
//~ cout<<"YES\n";
//~ exit(0);
//~ }
//~ return res;
//~ }
int check(int x){
assert(2 * x <= (int)todo.size());
for(int i=0;i<x;i++){
swap(a[todo[i<<1]], a[todo[i<<1|1]]);
}
int r = query(a);
if(r == n) exit(0);
for(int i=0;i<x;i++){
swap(a[todo[i<<1]], a[todo[i<<1|1]]);
} return r;
}
void solve(int N) { n = N;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
a.resize(n);
iota(a.begin(), a.end(), 1);
while(1){
shuffle(a.begin(), a.end(), rnd);
int q = query(a);
if(q == n) return;
if(!q) break;
}
vector<int> used(n);
int don = 0;
while(1){
//~ for(int i=0;i<n;i++){
//~ cout<<used[i]<<" ";
//~ } cout<<endl;
//~ for(int i=0;i<n;i++){
//~ cout<<a[i]<<" ";
//~ } cout<<endl;
todo.clear();
for(int i=0;i<n;i++){
if(used[i]) continue;
todo.push_back(i);
}
shuffle(todo.begin(), todo.end(), rnd);
int half = (int)todo.size() / 2;
if(check(half) == don) continue;
//~ cout<<"here"<<endl;
int l = 1, r = half;
while(l < r){
int m = (l + r) >> 1;
if(check(m) > don){
r = m;
} else {
l = m + 1;
}
} l--;
int i = todo[l<<1], j = todo[l<<1|1];
swap(a[i], a[j]);
int cost = query(a);
if(cost == n) return;
if(cost == don + 2){
used[i] = used[j] = 1; don += 2;
} else {
int p = -1;
for(int l=0;l<n;l++){
if(used[l] || i == l || j == l) continue;
p = l; break;
}
assert(~p);
swap(a[i], a[p]);
int tmp = query(a);
if(tmp == n) return;
swap(a[i], a[p]);
if(tmp < cost) used[i] = 1;
else used[j] = 1;
don++;
}
}
}
/*
8
3 6 5 7 8 1 4 2
*/
//~ signed main(){
//~ int n; cin>>n;
//~ B.resize(n);
//~ for(int i=0;i<n;i++) cin>>B[i];
//~ solve(n);
//~ }
Compilation message
mouse.cpp: In function 'int check(int)':
mouse.cpp:33:10: error: 'query' was not declared in this scope
33 | int r = query(a);
| ^~~~~
mouse.cpp: In function 'void solve(int)':
mouse.cpp:47:11: error: 'query' was not declared in this scope
47 | int q = query(a);
| ^~~~~
mouse.cpp:83:14: error: 'query' was not declared in this scope
83 | int cost = query(a);
| ^~~~~
