#include "xylophone.h"
using namespace std;
const int MN=5e3+5;
int arr[MN];
bool check2[MN];
int limit;
void solve(int n){
for(int i=1;i<=n;++i){
check2[i]=false;
}
limit=10000;
int l=1,r=n-1;
while(l<r){
int mid=l+r>>1;
int res=query(mid,n); --limit;
// cout<<"Case "<<mid<<' '<<n<<": "<<res<<'\n';
if(res==n-1) l=mid+1;
else r=mid;
}
int idx=l-1,num=n;
answer(idx,1);
check2[1]=true;
l=idx-2; r=idx+2;
if(idx>1){
int res=query(idx-1,idx); --limit;
answer(idx-1,res+1);
check2[res+1]=true;
}
int res=query(idx,idx+1); --limit;
answer(idx+1,res+1);
check2[res+1]=true;
for(int i=l;i>=1;--i){
int res=query(i,i+1); --limit;
if(arr[i+1]+res>=n||arr[i+1]+res<=1||check[arr[i+1]+res]){
answer(i,arr[i+1]-res);
check[arr[i+1]-res]=true; continue;
}
if(arr[i+1]-res>=n||arr[i+1]-res<=1||check[arr[i+1]-res]){
answer(i,arr[i+1]+res);
check[arr[i+1]+res]=true; continue;
}
if(limit==i-1){
if(!check2[arr[i+1]+res]&&arr[i+1]+res<n){
answer(i,arr[i+1]+res);
check2[arr[i+1]+res]=true;
}
else{
answer(i,arr[i+1]-res);
check2[arr[i+1]-res]=true;
}
}
else{
int res2=query(i,i+2); --limit;
if(res==res2){
if(arr[i+2]<arr[i+1]) arr[i]=arr[i+1]-res;
else arr[i]=arr[i+1]+res;
}
else{
if(arr[i+1]>arr[i+2]){
if(res2==arr[i+1]-arr[i+2]) arr[i]=arr[i+1]-res;
else arr[i]=arr[i+1]+res;
}
else{
if(res2==arr[i+2]-arr[i+1]) arr[i]=arr[i+1]+res;
else arr[i]=arr[i+1]-res;
}
}
answer(i,arr[i]); check2[arr[i]]=true;
}
}
for(int i=r;i<=n;++i){
int res=query(i-1,i); --limit;
if(arr[i-1]+res>n||arr[i-1]+res<=1||check[arr[i-1]+res]){
answer(i,arr[i-1]-res);
check[arr[i-1]-res]=true; continue;
}
if(arr[i-1]-res>n||arr[i-1]-res<=1||check[arr[i-1]-res]){
answer(i,arr[i-1]+res);
check[arr[i-1]+res]=true; continue;
}
if(limit==n-i){
if(!check2[arr[i-1]+res]&&arr[i-1]+res<=n){
answer(i,arr[i-1]+res);
check2[arr[i-1]+res]=true;
}
else{
answer(i,arr[i-1]-res);
check2[arr[i-1]-res]=true;
}
}
else{
int res2=query(i-2,i); --limit;
// cout<<"Case "<<i<<": "<<res<<' '<<res2<<'\n';
if(res==res2){
if(arr[i-2]<arr[i-1]) arr[i]=arr[i-1]-res;
else arr[i]=arr[i-1]+res;
}
else{
if(arr[i-2]<arr[i-1]){
if(res2==arr[i-1]-arr[i-2]) arr[i]=arr[i-1]-res;
else arr[i]=arr[i-1]+res;
}
else{
if(res2==arr[i-2]-arr[i-1]) arr[i]=arr[i-1]+res;
else arr[i]=arr[i-1]-res;
}
}
answer(i,arr[i]); check2[arr[i]]=true;
}
}
}
Compilation message
xylophone.cpp: In function 'void solve(int)':
xylophone.cpp:17:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
17 | int mid=l+r>>1;
| ~^~
xylophone.cpp:40:40: error: 'check' was not declared in this scope; did you mean 'check2'?
40 | if(arr[i+1]+res>=n||arr[i+1]+res<=1||check[arr[i+1]+res]){
| ^~~~~
| check2
xylophone.cpp:44:40: error: 'check' was not declared in this scope; did you mean 'check2'?
44 | if(arr[i+1]-res>=n||arr[i+1]-res<=1||check[arr[i+1]-res]){
| ^~~~~
| check2
xylophone.cpp:79:39: error: 'check' was not declared in this scope; did you mean 'check2'?
79 | if(arr[i-1]+res>n||arr[i-1]+res<=1||check[arr[i-1]+res]){
| ^~~~~
| check2
xylophone.cpp:83:39: error: 'check' was not declared in this scope; did you mean 'check2'?
83 | if(arr[i-1]-res>n||arr[i-1]-res<=1||check[arr[i-1]-res]){
| ^~~~~
| check2
xylophone.cpp:24:14: warning: unused variable 'num' [-Wunused-variable]
24 | int idx=l-1,num=n;
| ^~~
