Submission #295518

#TimeUsernameProblemLanguageResultExecution timeMemory
295518mode149256The Big Prize (IOI17_prize)C++14
20 / 100
7 ms368 KiB
#include <bits/stdc++.h> #include "prize.h" using namespace std; using vi = vector<int>; int N; int get(int l, int r, int kiek) { // int sqr = (int)sqrt(r - l + 1); // printf("l = %d, r = %d, kiek = %d\n", l, r, kiek); int m = (l + r) / 2; if (kiek <= 0) return -1; int st = max(l, m - kiek / 2); // ieskom did des [1] vi viso(2, 0); int ind = 0; for (int i = 0; i < kiek + 1 and st + i <= r; ++i) { vi ans = ask(st + i); if (ans[0] == ans[1] and ans[0] == 0) return st + i; if (ans[0] + ans[1] >= viso[0] + viso[1]) { ind = st + i; viso = ans; } } int left = get(l, ind - 1, kiek - viso[1]); int right = get(ind + 1, r, kiek - viso[0]); if (left != -1) return left; else return right; } int find_best(int n) { N = n; // if (n <= 5000) { // for (int i = 0; i < n; ++i) // { // vi ans = ask(i); // if (ans[0] == ans[1] and ans[0] == 0) // return i; // } // } vi viso(2, 0); int ind = 0; for (int i = 0; i < 475; ++i) { vi ans = ask(i); if (ans[0] == ans[1] and ans[0] == 0) return i; if (ans[0] + ans[1] >= viso[0] + viso[1]) { ind = i; viso = ans; } } return get(ind + 1, n - 1, viso[1]); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...