# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
101629 | 2019-03-19T05:29:37 Z | dantoh000 | popa (BOI18_popa) | C++14 | 0 ms | 0 KB |
//#include "popa.h" #include <bits/stdc++.h> using namespace std; void guess(int s, int e, int p, int* left, int* right){ //printf("at %d %d from %d\n",s,e,p); if (s > e){ left[s] = -1; right[s] = -1; return; } if (s == e){ if (e == p-1){ left[p] = e; } else if (s == p+1){ right[p] = s; } left[s] = right[s] = -1; return; } int ans = 0; int m = (s+e)/2; for (int i = m; i <= e; i++){ if (query(s,i,i,e)){ ans = i; break; } } if (ans == 0){ for (int i = s; i < m; i++){ if (query(s,i,i,e)){ ans = i; break; } } } if (e == p-1){ left[p] = ans; } else if (s == p+1){ right[p] = ans; } if (s <= ans-1) guess(s,ans-1,ans,left,right); else left[ans] = -1; if (ans+1 <= e) guess(ans+1,e,ans,left,right); else right[ans] = -1; return; } int solve(int N, int* left, int* right){ int s; for (int i = 0; i < N; i++){ if (query(0,i,i,N-1)){ s = i; break; } } guess(0,s-1,s,left,right); guess(s+1,N-1,s,left,right); return s; }