Submission #894684

#TimeUsernameProblemLanguageResultExecution timeMemory
894684Hugo1729Cave (IOI13_cave)C++11
13 / 100
317 ms828 KiB
#include "cave.h" #include <bits/stdc++.h> using namespace std; int n; vector<int> on{}, off{}; int query(int a, int b,int cor){ int ans[n]; if(cor){ fill(ans,ans+n,0); for(int i=a;i<=b;i++) ans[i]++; }else{ fill(ans,ans+n,1); for(int i=a;i<=b;i++) ans[i]--; } for(int p : off) ans[p]=0; for(int p : on) ans[p]=1; int ret = tryCombination(ans); if (ret==-1) return 0; return ret; } void exploreCave(int N) { n=N; int D[N],S[N]; for(int p=0;p<N;p++){ int lo=0,hi=n-1,cor=1; if(query(lo,hi,cor)==p) cor--; while(lo!=hi){ int mid=(lo+hi)/2; int q=query(lo,mid,cor); // cout << '(' << lo << hi << q << ')'; if(q==p) lo=mid+1; else hi = mid; } S[lo] = cor; D[lo] = p; if(cor) on.push_back(lo); else off.push_back(lo); } // int a; cin >> a; answer(S,D); return; }
#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...