Submission #1056803

#TimeUsernameProblemLanguageResultExecution timeMemory
1056803phoenixThe Big Prize (IOI17_prize)C++17
91.72 / 100
32 ms5524 KiB
#include "prize.h" #include <bits/stdc++.h> using namespace std; const int N = 200200; const int B = 512; vector<int> arr[N]; vector<int> ASK(int p) { if (arr[p].empty()) arr[p] = ask(p); return arr[p]; } int sum(int i) { return ASK(i)[0] + ASK(i)[1]; } int find_best(int n) { int val = sum(0); for (int i = 0; i < min(n, B); i++) { if (!sum(i)) return i; val = max(val, sum(i)); } int cnt = 0; for (int i = 0; i < B; i++) cnt += (sum(i) < val); for (int it = B; it < n; it += B) { int rb = min(it + B - 1, n - 1), k = 0; if (sum(rb) == val && arr[rb][0] == cnt) continue; while (rb >= it && sum(rb) < val) { if (!sum(rb)) return rb; k++; rb--; } int i = it, del = arr[rb][0]; while (i < rb && cnt < arr[rb][0]) { while (i < rb && sum(i) < val) { if (!sum(i)) return i; cnt++; i++; } if (cnt == arr[rb][0]) break; int l = i, r = rb; while (r - l > 1) { int mid = (l + r) / 2; if (ASK(mid) == ASK(i)) l = mid; else { if (!sum(mid)) return mid; r = mid; } } i = r; } cnt += k; } return 0; }

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:41:15: warning: unused variable 'del' [-Wunused-variable]
   41 |   int i = it, del = arr[rb][0];
      |               ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...