Submission #292931

#TimeUsernameProblemLanguageResultExecution timeMemory
292931SaboonThe Big Prize (IOI17_prize)C++17
0 / 100
104 ms364 KiB
#include "prize.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; int Max = 0; int solve(int l, int r, int cnt, int pre = 0, int suf = 0){ if (cnt == r-l or l >= r) return -1; if (l+1 == r){ vector<int> res = ask(l); if (res[0]+res[1] == 0) return l; return -1; } for (int mid = (l+r)>>1; mid < r; mid++){ vector<int> res = ask(mid); if (res[0]+res[1] == 0) return mid; if (res[0]+res[1] == Max){ int ret = solve(l,mid,res[0]-pre, pre, res[1]+1); if (ret != -1) return ret; return solve(mid+1, r, res[1]-suf, res[0]+1, suf); } } for (int mid = ((l+r)>>1)-1; mid >= l; mid--){ vector<int> res = ask(mid); if (res[0]+res[1] == 0) return mid; if (res[0]+res[1] == Max){ int ret = solve(l,mid,res[0]-pre, pre, res[1]+1); if (ret != -1) return ret; return solve(mid+1, r, res[1]-suf, res[0]+1, suf); } } return -1; } int find_best(int n){ if (n <= 5000){ for(int i = 0; i < n; i++) { vector<int> res = ask(i); if(res[0] + res[1] == 0) return i; } } for (int i = 0; i < min(n,500); i++){ vector<int> res = ask(i); Max = max(Max, res[0]+res[1]); if (res[0] + res[1] == 0) return i; } return solve(0, n, n-Max); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...