#include <iostream> #include <cmath> #include <algorithm> #include <map> #include <unordered_map> #include <vector> #include <iomanip> #include <string> #include <queue> #include <set> #include <deque> #include "xylophone.h" using namespace std; static const int N_MAX = 5000; static const int Q_MAX = 10000; static int N; static int A[N_MAX]; static bool used[N_MAX]; static int query_c; static int answer_c; void solve(int n){ int l=1; int h=n; int m=(l+h)/2; while (l<h){ int x=query(1,m); if (x==n-1){ h=m; } else{ l=m+1; } m=(l+h)/2; } int r=m; l=1; h=r; m=(l+h+1)/2; while (l<h){ int x=query(m,r); if (x==n-1){ l=m; } else{ h=m-1; } m=(l+h+1)/2; } answer(l,1); answer(r,n); vector<int>a(n+1); a[l]=1; a[r]=n; map<pair<int,int>,int>d; d[{l,l}]=0; vector<int>vi(n+1); vi[1]=1; vi[n]=1; for (int i=l-1;i>=1;i--){ int x=query(i,i+1); if (a[i+1]-x<1 or vi[a[i+1]-x]){ a[i]=a[i+1]+x; vi[a[i+1]+x]=1; answer(i,a[i+1]+x); continue; } if (a[i+1]+x>n or vi[a[i+1]+x]){ a[i]=a[i+1]-x; vi[a[i+1]-x]=1; answer(i,a[i+1]-x); continue; } int y=query(i,i+2); int z=abs(a[i+1]-a[i+2]); if (y>z){ if (a[i+1]>a[i+2]){ a[i]=a[i+1]+x; vi[a[i+1]+x]=1; answer(i,a[i+1]+x); } else{ a[i]=a[i+1]-x; vi[a[i+1]-x]=1; answer(i,a[i+1]-x); } } else{ if (a[i+1]>a[i+2]){ a[i]=a[i+1]-x; vi[a[i+1]-x]=1; answer(i,a[i+1]-x); } else{ a[i]=a[i+1]+x; vi[a[i+1]+x]=1; answer(i,a[i+1]+x); } } } for (int i=l+1;i<r;i++){ int x=query(i-1,i); if (a[i-1]-x<1 or vi[a[i-1]-x]){ a[i]=a[i-1]+x; vi[a[i-1]+x]=1; answer(i,a[i-1]+x); continue; } if (a[i-1]+x>n or vi[a[i-1]+x]){ a[i]=a[i-1]-x; vi[a[i-1]-x]=1; answer(i,a[i-1]-x); continue; } int y=query(i-2,i); int z=abs(a[i-1]-a[i-2]); if (y>z){ if (a[i-1]>a[i-2]){ a[i]=a[i-1]+x; vi[a[i-1]+x]=1; answer(i,a[i-1]+x); } else{ a[i]=a[i-1]-x; vi[a[i-1]-x]=1; answer(i,a[i-1]-x); } } else{ if (a[i-1]>a[i-2]){ a[i]=a[i-1]-x; vi[a[i-1]-x]=1; answer(i,a[i-1]-x); } else{ a[i]=a[i-1]+x; vi[a[i-1]+x]=1; answer(i,a[i-1]+x); } } } for (int i=r+1;i<=n;i++){ int x=query(i-1,i); if (a[i-1]-x<1 or vi[a[i-1]-x]){ a[i]=a[i-1]+x; vi[a[i-1]+x]=1; answer(i,a[i-1]+x); continue; } if (a[i-1]+x>n or vi[a[i-1]+x]){ a[i]=a[i-1]-x; vi[a[i-1]-x]=1; answer(i,a[i-1]-x); continue; } int y=query(i-2,i); int z=abs(a[i-1]-a[i-2]); if (y>z){ if (a[i-1]>a[i-2]){ a[i]=a[i-1]+x; vi[a[i-1]+x]=1; answer(i,a[i-1]+x); } else{ a[i]=a[i-1]-x; vi[a[i-1]-x]=1; answer(i,a[i-1]-x); } } else{ if (a[i-1]>a[i-2]){ a[i]=a[i-1]-x; vi[a[i-1]-x]=1; answer(i,a[i-1]-x); } else{ a[i]=a[i-1]+x; vi[a[i-1]+x]=1; answer(i,a[i-1]+x); } } } return; }