Submission #703035

#TimeUsernameProblemLanguageResultExecution timeMemory
703035beepbeepsheepXylophone (JOI18_xylophone)C++17
100 / 100
67 ms432 KiB
#include "xylophone.h" #include <bits/stdc++.h> using namespace std; bool vis[5005]; int arr[5005]; #define ll long long int eval(ll res, ll res2, ll a, ll b){ if (a+res==b+res2){ return 1; } if (a-res==b-res2){ return -1; } if (res==res2){ if (a<b) return 1; else return -1; } else{ if (a<b) return 1; return -1; } } void solve(int N) { int l=1,r=N,m; while (l!=r-1){ m=(l+r)>>1; if (query(m,N)==N-1) l=m; else r=m; } vis[1]=true; arr[l]=1; if (l==1){ arr[2]=query(l,l+1)+1; vis[arr[2]]=true; for (int i=3;i<=N;i++){ int res=query(i-1,i); if (arr[i-1]-res<1 || vis[arr[i-1]-res]){ arr[i]=res+arr[i-1]; } else if (res+arr[i-1]>N || vis[res+arr[i-1]]){ arr[i]=arr[i-1]-res; } else{ int res2=query(i-2,i); arr[i]=arr[i-1]+res*eval(res,res2,arr[i-1],arr[i-2]); } vis[arr[i]]=true; } } else{ arr[l+1]=query(l,l+1)+1; arr[l-1]=query(l-1,l)+1; vis[arr[l+1]]=true; vis[arr[l-1]]=true; for (int i=l+2;i<=N;i++){ int res=query(i-1,i); if (arr[i-1]-res<1 || vis[arr[i-1]-res]){ arr[i]=res+arr[i-1]; } else if (res+arr[i-1]>N || vis[res+arr[i-1]]){ arr[i]=arr[i-1]-res; } else{ int res2=query(i-2,i); arr[i]=arr[i-1]+res*eval(res,res2,arr[i-1],arr[i-2]); } vis[arr[i]]=true; } for (int i=l-2;i>=1;i--){ int res=query(i,i+1); if (arr[i+1]-res<1 || vis[arr[i+1]-res]){ arr[i]=res+arr[i+1]; } else if (res+arr[i+1]>N || vis[res+arr[i+1]]){ arr[i]=arr[i+1]-res; } else{ int res2=query(i,i+2); arr[i]=arr[i+1]+res*eval(res,res2,arr[i+1],arr[i+2]); } vis[arr[i]]=true; } } //for (int i=1;i<=N;i++) cerr<<arr[i]<<' '; for (int i=1;i<=N;i++) answer(i,arr[i]); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...