#include "prize.h" #define K 500 using namespace std; typedef vector<int> vi; int max(int a, int b) { return a > b ? a : b; } int lollipop; int solve(int l, int r, int l_, int r_) { int m, i; if (l_ == r_) return -1; m = (l + r) / 2; for (i = m; i < r; i++) { vi a = ask(i); if (a[0] + a[1] == 0) return i; if (a[0] + a[1] == lollipop) { int i_; if ((i_ = solve(l, m, l_, a[0] - (i - m))) != -1) return i_; return solve(i + 1, r, a[0], r_); } } for (i = m - 1; i >= l; i--) { vi a = ask(i); if (a[0] + a[1] == 0) return i; if (a[0] + a[1] == lollipop) return solve(l, i, l_, a[0]); } return -1; } int kk[K + 1]; int find_best(int n) { int i, cnt; for (i = 0; i < n && i <= K; i++) { vi a = ask(i); if ((kk[i] = a[0] + a[1]) == 0) return i; lollipop = max(lollipop, a[0] + a[1]); } cnt = 0; for (i = 0; i <= K; i++) if (kk[i] != lollipop) cnt++; return solve(i, n, cnt, lollipop); }