Submission #61770

#TimeUsernameProblemLanguageResultExecution timeMemory
61770zadrgaThe Big Prize (IOI17_prize)C++14
20 / 100
136 ms5620 KiB
#include "prize.h" #include <bits/stdc++.h> using namespace std; #define pb push_back #define mp make_pair #define fi first #define se second #define INF (1 << 30) #define MOD (1000 * 1000 * 1000 + 7) #define maxn 201111 #define SQRT 450 #define BUCKET 5000 typedef long long ll; typedef long double ld; typedef pair<int, int> pii; int max_val; int ans; bool used[maxn]; vector<int> v[maxn]; vector<int> ASK(int x){ if(!used[x]){ v[x] = ask(x); used[x] = 1; } return v[x]; } void solve(int L, int D){ if(ans != -1 || L > D) return; int l = -1, d = -1; vector<int> left, right; for(int i = L; i <= D; i++){ left = ASK(i); if(left[0] + left[1] == 0){ ans = i; return; } if(left[0] + left[1] == max_val){ l = i; break; } } if(l == -1) return; for(int i = D; i > l; i--){ right = ASK(i); if(right[0] + right[1] == 0){ ans = i; return; } if(right[0] + right[1] == max_val){ d = i; break; } } if(d == -1) return; int num = left[1] - right[1]; if(num == 0) return; int mid = (l + d) / 2; solve(l + 1, mid); solve(mid + 1, d - 1); } int find_best(int n){ max_val = ans = -1; for(int i = 0; i < min(SQRT + 50, n); i++){ vector<int> ret = ASK(i); max_val = max(max_val, ret[0] + ret[1]); } solve(0, n - 1); return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...