Submission #764640

#TimeUsernameProblemLanguageResultExecution timeMemory
764640vjudge1Xylophone (JOI18_xylophone)C++17
100 / 100
61 ms328 KiB
#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]=3; ans[2]=1; ans[3]=2; ans[4]=5; ans[5]=4; // 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){ if(n==1){ answer(1,1); return; } for(int i=1;i<=n;++i){ check2[i]=false; } limit=10000; int l=1,r=n; /* int idx=n-1; for(int i=2;i<idx;++i){ int res=query(i,n); if(res!=n-1){ idx=i-1; break; } } */ 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'; arr[idx]=1; check2[1]=true; l=idx-2,r=idx+2; if(idx>1){ int res=query(idx-1,idx); --limit; arr[idx-1]=res+1; check2[res+1]=true; } int res=query(idx,idx+1); --limit; arr[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]){ arr[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]){ arr[i]=arr[i+1]+res; check2[arr[i+1]+res]=true; continue; } if(limit==i-1+(n-r+1)){ if(!check2[arr[i+1]+res]&&arr[i+1]+res<n){ arr[i]=arr[i+1]+res; check2[arr[i+1]+res]=true; } else{ arr[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; } } 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'; arr[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'; arr[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){ arr[i]=arr[i-1]+res; check2[arr[i-1]+res]=true; } else{ arr[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; } } check2[arr[i]]=true; } } for(int i=1;i<=n;++i){ answer(i,arr[i]); } } /* 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)100;++numtest){ cout<<"Running on test "<<numtest<<": "; int n; n=rd(1,10); 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 (stderr)

xylophone.cpp:214:5: warning: "/*" within comment [-Wcomment]
  214 |     /*
      |      
xylophone.cpp: In function 'void solve(int)':
xylophone.cpp:92:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   92 |   int mid=l+r>>1;
      |           ~^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...