Submission #1165588

#TimeUsernameProblemLanguageResultExecution timeMemory
1165588abcdxyz123Library (JOI18_library)C++17
0 / 100
18 ms420 KiB
#include"library.h" #include<bits/stdc++.h> #define maxn 1005 #define pi pair<int,int> #define fi first #define se second using namespace std; int n; int a[maxn]; int nho[maxn]; vector<int>REAL_ANS; /* int Query(const std::vector<int>& M) { //cout<<"+> Query "; //for(int x:M)cout<<x<<' '; //cout<<'\n'; int ds=0; int pre=0; for(int x:REAL_ANS) { if(M[x-1]==0) { if(pre) { ds++; pre=0; } } else { pre++; } } if(pre)ds++; //cout<<ds<<'\n'; return ds; } void Answer(const std::vector<int>& res) { cout<<"+> Answer "; for(int x:res)cout<<x<<' '; cout<<'\n'; } */ 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) { 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; 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) { 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 ; } n=N; a[1]=FindA1(); //cout<<a[1]<<'\n'; a[2]=FindA2(a[1]); //cout<<a[2]<<'\n'; //cout<<ask(3,5)<<'\n'; for(int i=3;i<n;i++) { int L=FindAdjSecond(a[i-1],1,n); int R=FindAdjFirst(a[i-1],1,n); //cout<<L<<' '<<R<<'\n'; if(a[i-2]==L)a[i]=R; else a[i]=L; } 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); } /* int main() { REAL_ANS={1,2}; Solve(2); } */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...