Submission #553951

#TimeUsernameProblemLanguageResultExecution timeMemory
553951timreizinThe Big Prize (IOI17_prize)C++17
97.42 / 100
47 ms5244 KiB
#include "prize.h" #include <iostream> using namespace std; int find_best(int n) { vector<vector<int>> mem(n); int prev = -1; int sum = 0; for (int j = 0; j < min(500, n); ++j) { mem[j] = ask(j); if (mem[j][0] + mem[j][1] == 0) return j; sum = max(sum, mem[j][0] + mem[j][1]); } for (int i = 1;; ++i) { int l = 0, r = n - 1; //first with not max level while (l < r) { int m = (l + r) >> 1; if (m <= prev) { l = m + 1; continue; } if (mem[m].empty()) mem[m] = ask(m); if (mem[m][0] + mem[m][1] == 0) return m; if ((mem[m][0] + mem[m][1] == sum && mem[m][0] < i) || m <= prev) l = m + 1; else r = m; } prev = l; if (mem[prev].empty()) mem[prev] = ask(prev); if (mem[prev][0] + mem[prev][1] == 0) return prev; } } //1 2 5 26 677 - mins //1 4 21 446 200000 - maxs
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...