Submission #1165605

#TimeUsernameProblemLanguageResultExecution timeMemory
1165605abcdxyz123Library (JOI18_library)C++20
0 / 100
0 ms412 KiB
#include"library.h" #include<bits/stdc++.h> #define maxn 1005 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(vector<int> res) { //cout<<"+> Answer "; //for(int x:res)cout<<x<<' '; //cout<<'\n'; //cout<<"+> My sol "; //for(int x:REAL_ANS)cout<<x<<' '; //cout<<'\n'; int flag=2; for(int i=1;i<=n;i++) { if(res[i-1]!=REAL_ANS[i-1]) { flag--; break; } } reverse(res.begin(),res.end()); for(int i=1;i<=n;i++) { if(res[i-1]!=REAL_ANS[i-1]) { flag--; break; } } if(flag>=1) { } else { cout<<"Flase"<<'\n'; for(int x:res)cout<<x<<' '; exit(0); } } */ 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; 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(); //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[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(i); } Answer(ans); } /* bool shouldSkip() { //return 0; return (1.0 * clock() / CLOCKS_PER_SEC >=1.0); } int main() { int N=500; for(int i=1;i<=N;i++)REAL_ANS.push_back(i); do { Solve(N); if(shouldSkip())break; } while(next_permutation(REAL_ANS.begin(),REAL_ANS.end())); } */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...