#include <bits/stdc++.h> #include "grader.h" int query(vector<int> v); int n; mt19937 rnd(23232); bool yey[300]; void solve(int N){ n=N; vector<int>perm; for(int q=1;q<=n;q++){ perm.push_back(q); } while(true){ shuffle(perm.begin(),perm.end(),rnd); if(query(perm)==0)break; } // cout<<"PERM"<<endl; // for(auto x : perm){ // cout<<x<<" "; // } // cout<<endl; int benar=0,prv=0; while(true){ vector<int>slh; for(int q=0;q<n;q++){ if(!yey[q]){ slh.push_back(q); } } if(slh.empty())break; vector<int>tmp; while(true){ tmp=perm; shuffle(slh.begin(),slh.end(),rnd); for(int q=1;q<slh.size();q+=2){ swap(tmp[slh[q-1]],tmp[slh[q]]); } int apa=query(tmp); if(apa==n)return; if(apa>prv)break; } // for(auto x : slh){ // cout<<x<<" "; // } // cout<<endl; int l=0,r=slh.size()/2; int brp=0; while(l<=r){ int mid=(l+r)/2; tmp=perm; for(int q=0;q<mid;q++){ swap(tmp[slh[2*q]],tmp[slh[2*q+1]]); } int apa=query(tmp); if(apa==n)return; if(apa>prv){ brp=mid; r=mid-1; } else{ l=mid+1; } } brp--; int a=slh[2*brp],b=slh[2*brp+1]; swap(perm[a],perm[b]); int tot=query(perm); if(tot==n)return; if(tot-prv==2){ yey[a]=yey[b]=true; benar=a; prv=tot; continue; } if(benar){ tmp=perm; swap(tmp[a],tmp[benar]); int apa=query(tmp); if(apa==n)return; if(apa==tot-1){ yey[b]=true; } else{ yey[a]=true; } prv=tot; } else{ int lain=1; while(lain==a || lain==b)lain++; tmp=perm; swap(tmp[lain],tmp[b]); int apa=query(tmp); if(apa==n)return; if(apa<tot){ yey[b]=true; benar=b; } else{ yey[a]=true; benar=a; } prv=tot; } } }