Submission #246016

#TimeUsernameProblemLanguageResultExecution timeMemory
246016thecodingwizardThe Big Prize (IOI17_prize)C++11
20 / 100
95 ms512 KiB
#include "prize.h" using namespace std; #define vi vector<int> int biggestCt = 0; int solve(int l, int r, int numLeft, int numRight) { if (l > r) return -1; if (numLeft + numRight == biggestCt) return -1; for (int mid = (l+r)/2; mid <= r; mid++) { vi res = ask(mid); int sum = res[0] + res[1]; if (sum == 0) return mid; if (sum != biggestCt) continue; int ans = solve(mid+1, r, res[0], numRight); if (ans != -1) return ans; return solve(l, (l+r)/2-1, numLeft, res[1] + mid-(l+r)/2); } for (int mid = (l+r)/2-1; mid >= l; mid--) { vi res = ask(mid); int sum = res[0] + res[1]; if (sum == 0) return mid; if (sum != biggestCt) continue; int ans = solve(l, mid-1, numLeft, res[1]); if (ans != -1) return ans; break; } return -1; } int find_best(int n) { for (int i = 0; i < min(n, 473); i++) { vi res = ask(i); if (res[0] + res[1] == 0) return i; biggestCt = max(biggestCt, res[0] + res[1]); if (biggestCt >= 15) break; } return solve(0, n-1, 0, 0); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...