#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,l); if (!d[{i+1,l}]){ d[{i+1,l}]=query(i+1,l); } int z=d[{i+1,l}]; if (z>y){ 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(l,i); if (!d[{i-1,l}]){ d[{i-1,l}]=query(l,i-1); } int z=d[{i-1,l}]; if (z>y){ 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(r,i); if (!d[{i-1,l}]){ d[{i-1,l}]=query(r,i-1); } int z=d[{i-1,l}]; if (z>y){ 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; }