#include <iostream> #include <vector> #include "prize.h" using namespace std; int tot; vector<int> Ans, res; // vector<int> ask(int id){ // return {}; // } void Solve(int l, int r, int k, int cnt){ vector<int> rs; if (cnt == 0 or l == r) return; // cout<<l<<" "<<r<<" "<<cnt<<endl; int mid = (l + r) / 2; rs = ask(mid); // cout<<l<<" "<<mid<<" "<<r<<" "<<k<<" "<<cnt<<" "<<rs[0]<<" "<<rs[1]<<endl; if (rs[0] + rs[1] != tot){ int m1 = mid + 1; while (m1 < r){ rs = ask(m1); if (rs[0] + rs[1] == tot) break; m1++; } // cout<<"here "<<m1<<" "<<rs[0]<<" "<<rs[1]<<endl; if (m1 == r) Solve(l, mid, k, cnt - (m1 - mid)); else Solve(l, mid, k, k - rs[1] - (m1 - mid)); for (int i=mid;i<m1;i++) Ans.push_back(i); Solve(m1, r, rs[1], cnt - (k - rs[1])); return; } Solve(l, mid, k, k - rs[1]); Solve(mid, r, rs[1], cnt - (k - rs[1])); } int find_best(int n){ srand(time(0)); for (int i=1;i<=20;i++){ int id = rand() % n; res = ask(id); tot = max(tot, res[0] + res[1]); } int i = 0; while (1){ res = ask(i); if (res[0] + res[1] == tot) break; Ans.push_back(i); i++; } Solve(i, n, tot - i, tot - i); for (int i : Ans){ res = ask(i); if (res[0] + res[1] == 0) return i; } return 0; }