#include "xylophone.h"
//#include<bits/stdc++.h>
using namespace std;
/*
#define taskname "template"
#define ll long long
#define ld double
#define fi first
#define se second
#define vi vector<int>
#define pii pair<int,int>
#define vii vector<pii>
#define vvi vector<vi>
#define pb push_back
#define eb emplace_back
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rd(ll min1,ll max1){
assert(min1<=max1);
ll res=rng()*1LL*rng()%(max1-min1+1);
if(res<0) res=-res;
return min1+res;
}
*/
const int MN=5e3+5;
int arr[MN],ans[MN];
bool check[MN];
bool check2[MN];
int limit;
/*
void stress(int n){
for(int i=1;i<=n;++i){
ans[i]=0;
check[i]=false;
}
if(n<=2){
ans[1]=1;
ans[2]=2;
return;
}
int idx=rd(2,n);
ans[idx]=n; //cout<<idx<<'\n';
// cout<<idx<<endl;
if(1>idx-1) cout<<"!!!!!!!!!!!!!!!!! "<<idx<<endl;
int idx1=rd(1,idx-1);
ans[idx1]=1;
check[1]=check[n]=true;
for(int i=1;i<=n;++i){
if(ans[i]) continue;
if(2>n-1) cout<<"Case "<<i<<": "<<endl;
ll res=rd(2,n-1);
if(check[res]){
--i; continue;
}
check[res]=true; ans[i]=res;
}
// ans[1]=2; ans[2]=1; ans[3]=3;
// ans[1]=4; ans[2]=6; ans[3]=3; ans[4]=1; ans[5]=7;
// ans[6]=10; ans[7]=2; ans[8]=8; ans[9]=5; ans[10]=9;
}
int query(int tl,int tr){
return *max_element(ans+tl, ans+tr+1) - *min_element(ans+tl, ans+tr+1);
}
void answer(int p,int value){
arr[p]=value;
}
*/
void solve(int N){
int n=N;
if(n==1){
answer(1,1); return;
}
for(int i=1;i<=n;++i){
check2[i]=false;
}
limit=10000;
int l=1,r=n;
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;
// cout<<idx<<'\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||check2[arr[i+1]+res]){
answer(i,arr[i+1]-res);
check2[arr[i+1]-res]=true; continue;
}
if(arr[i+1]-res>=n||arr[i+1]-res<=1||check2[arr[i+1]-res]){
answer(i,arr[i+1]+res);
check2[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;
// cout<<"Case "<<i<<": "<<res<<' '<<res2<<endl;
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||check2[arr[i-1]+res]){
// cout<<"mmb"<<'\n';
answer(i,arr[i-1]-res);
check2[arr[i-1]-res]=true; continue;
}
if(arr[i-1]-res>n||arr[i-1]-res<=1||check2[arr[i-1]-res]){
// cout<<"mmg"<<'\n';
answer(i,arr[i-1]+res);
check2[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;
}
}
}
/*
int test(int n){
for(int i=1;i<=n;++i){
if(arr[i]!=ans[i]){
return 0;
}
}
return 1;
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// freopen("output.txt","w",stdout);
/*
freopen(taskname".inp","r",stdin);
freopen(taskname".out","w",stdout);
int last=1;
for(int numtest=1;numtest<=(int)1e5;++numtest){
cout<<"Running on test "<<numtest<<": ";
int n; n=rd(1,100);
stress(n);
for(int i=1;i<=n;++i){
cout<<ans[i]<<' ';
} cout<<endl;
solve(n);
last&=test(n);
cout<<"Question left: "<<limit<<endl<<endl;
if(!last){
cout<<"Wrong answer on test "<<numtest<<endl;
cout<<"Your array: ";
for(int i=1;i<=n;++i){
cout<<arr[i]<<' ';
}cout<<endl;
cout<<"Answer array: ";
for(int i=1;i<=n;++i){
cout<<ans[i]<<' ';
}cout<<endl;
return 0;
}
}
cout<<"Accepted!";
}
*/
Compilation message
xylophone.cpp:202:5: warning: "/*" within comment [-Wcomment]
202 | /*
|
xylophone.cpp: In function 'void solve(int)':
xylophone.cpp:84:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
84 | int mid=l+r>>1;
| ~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
208 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
208 KB |
Wrong Answer [4] |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
208 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
208 KB |
Wrong Answer [4] |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
208 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
208 KB |
Wrong Answer [4] |
| 3 |
Halted |
0 ms |
0 KB |
- |
