Submission #1015004

#TimeUsernameProblemLanguageResultExecution timeMemory
1015004MardonbekhazratovCave (IOI13_cave)C++17
100 / 100
245 ms1112 KiB
#include "cave.h" #include<iostream> #include<set> #include<vector> const int maxN=5e3+1; int n; int S[maxN],D[maxN]; std::set<int>s; void solve(int x){ int ans=tryCombination(S); std::vector<int>a; for(int k:s) a.push_back(k); if(ans==x){ int l=0,r=(int)a.size()-1; while(r>l){ int mid=(l+r)/2; for(int j=0;j<=mid;j++){ S[a[j]]=1; } if(tryCombination(S)!=x) r=mid; else l=mid+1; for(int j=0;j<=mid;j++){ S[a[j]]=0; } } D[a[l]]=x; S[a[l]]=1; s.erase(a[l]); return; } int l=0,r=(int)a.size()-1; while(r>l){ int mid=(l+r)/2; for(int j=0;j<=mid;j++){ S[a[j]]=1; } if(tryCombination(S)==x) r=mid; else l=mid+1; for(int j=0;j<=mid;j++){ S[a[j]]=0; } } D[a[l]]=x; S[a[l]]=0; s.erase(a[l]); } void exploreCave(int N) { n=N; for(int i=0;i<n;i++) s.insert(i),D[i]=-1,S[i]=0; for(int i=0;i<n;i++){ solve(i); } answer(S,D); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...