#include "prize.h"
#include <tuple>
#include <queue>
using namespace std;
typedef tuple<float,int,int> fii;
int n,s,e,mid;
float amount;
std::vector<int> res;
int find_best(int n) {
::n = n;
// std::vector<int> res = ask(i);
priority_queue<fii,vector<fii>,less<fii>> q;
res = ask(n / 2);
if(res[0] + res[1] == 0) {
return n / 2;
}
q.push({(float) res[0] / (float) (n / 2),0, n / 2 - 1});
q.push({(float) res[1] / (float) (n - n / 2 - 1),n / 2 + 1,n - 1});
while(!q.empty()) {
tie(amount,s,e) = q.top();
q.pop();
if(s > e) {
continue;
}
mid = (e + s) / 2;
res = ask(mid);
if(res[0] + res[1] == 0) {
return mid;
}
q.push({(float) res[0] / (float) (mid - s),s,mid - 1});
q.push({(float) res[1] / (float) (e - mid),mid + 1,e});
}
return 0;
}
