#include "prize.h" #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #define FOR(i, x, y) for (int i = x; i < y; i++) typedef long long ll; using namespace std; using namespace __gnu_pbds; typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set; int find_best(int n) { int mx = 0, worst; vector<int> worst_res; // Finds the first lollipop for (worst = 0; worst < min(n, 474); worst++) { vector<int> res = ask(worst); if (res[0] + res[1] > mx) { mx = res[0] + res[1]; worst_res = res; } else if (res[0] + res[1] == 0) return worst; } // Binary searches for the other prizes indexed_set remaining; FOR(i, worst, n) remaining.insert(i); while (remaining.size()) { int l = 0, r = remaining.size() - 1; while (l != r) { int mid = (l + r + 1) / 2; int pos = *remaining.find_by_order(mid); vector<int> res = ask(pos); if (res[0] + res[1] == 0) return pos; else if (res[0] + res[1] == mx) { if (res[1] == worst_res[1]) { while (*remaining.begin() <= pos) remaining.erase(remaining.begin()); break; } else r = mid - 1; } else { remaining.erase(pos); break; } } } return -1; }