Submission #1165642

#TimeUsernameProblemLanguageResultExecution timeMemory
1165642abcdxyz123Library (JOI18_library)C++20
19 / 100
148 ms432 KiB
#include"library.h" #include<bits/stdc++.h> using namespace std; int n; int a[1005]; int nho[1005]; int FindA1() { vector<int>mask; for(int i=1;i<=n;i++) { mask.push_back(1); } for(int i=1;i<=n;i++) { mask[i-1]=0; if(Query(mask)==1)return i; mask[i-1]=1; } assert(false); } int FindA2(int a1) { vector<int>mask; for(int i=1;i<=n;i++) { mask.push_back(0); } mask[a1-1]=1; for(int i=1;i<=n;i++) { if(i==a1)continue; mask[i-1]=1; if(Query(mask)==1)return i; mask[i-1]=0; } assert(false); } int ask(int lim,int x) { if(x==lim&&lim==1)return 0; vector<int>mask; for(int i=1;i<=lim;i++) { mask.push_back(1); } for(int i=lim+1;i<=n;i++) { mask.push_back(0); } mask[x-1]=0; int tmp=Query(mask); mask[x-1]=1; int delta =Query(mask)-tmp; if(delta==-1)return 2; else if(delta==0)return 1; else if(delta==1)return 0; return 0; } int FindAdjSecond(int x,int lo,int hi) { while(hi-lo>1) { int mid=(lo+hi)/2; if(ask(mid,x)>=2) { hi=mid; } else { lo=mid; } } return hi; } int FindAdjFirst(int x,int lo,int hi) { if(ask(lo,x)==1)return lo; while(hi-lo>1) { int mid=(lo+hi)/2; if(ask(mid,x)>=1) { hi=mid; } else { lo=mid; } } return hi; } void Solve(int N) { n=N; if(N==1) { vector<int>tmp; tmp.push_back(1); Answer(tmp); return ; } else if(N==2) { vector<int>tmp; tmp.push_back(1); tmp.push_back(2); Answer(tmp); return ; } a[1]=FindA1(); a[2]=FindA2(a[1]); for(int i=3;i<n;i++) { int L=FindAdjSecond(a[i-1],1,n); int R=FindAdjFirst(a[i-1],1,n); if(a[i-2]==L)a[i]=R; else a[i]=L; } for(int i=1;i<=n;i++) { nho[i]=0; } for(int i=1;i<n;i++) { nho[a[i]]=1; } for(int i=1;i<=n;i++) { if(nho[i]==0) { a[n]=i; break; } } vector<int>ans; for(int i=1;i<=n;i++) { ans.push_back(a[i]); } Answer(ans); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...