#include "prize.h"
#include <vector>
#include <iostream>
#include <cassert>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
#define sz(x) int(x.size())
const int mx = 200'000;
int lim = 50'000;
int n;
int prizes = 0; //lollipops are not prizes
vvi qr(mx, vi(0));
int askcount = 0;
vi query(int i)
{
// cerr << "query " << i << '\n';
cerr << sz(qr[i]) << '\n';
if(qr[i].empty())
{
// cerr << "trigger\n";
askcount++;
if(!(askcount <= 10'000))
while(1);
qr[i] = ask(i);
}
return qr[i];
}
bool isprize(int i)
{
query(i);
if(qr[i][0] + qr[i][1] != prizes)
return 1;
else
return 0;
}
bool isdiamond(int i)
{
query(i);
return qr[i][0] + qr[i][1] == 0;
}
void solve(int l, int r)
{
if(r < l)
return;
// cerr << "solve " << l << ' ' << r << '\n';
query(l);
query(r);
if(l == r)
return;
// cerr << "hello\n";
if(isprize(l))
{
l++;
solve(l, r);
return;
}
if(isprize(r))
{
r--;
solve(l, r);
return;
}
int m = (l+r)/2;
query(m);
// cerr << "check\n";
int ml = m, mr = m;
while(isprize(ml))
ml--;
query(ml);
// cerr << "check\n";
// cerr << l << " : " << ml << '\n';
// cerr << sz(qr[l]) << ' ' << sz(qr[ml]) << '\n';
if(ml != l && qr[ml][0] - qr[l][0] >= 1)
{
// cerr << "call " << l+1 << ' ' << ml-1 << '\n';
solve(l+1, ml-1);
}
while(isprize(mr))
mr++;
query(mr);
// cerr << "check 5\n";
// cerr << r << " : " << mr << '\n';
if(mr != r && qr[r][0] - qr[mr][0] >= 1)
solve(mr+1, r-1);
}
int find_best(int n_)
{
n = n_;
lim = 1;
while(lim*lim <= n)
lim++;
// cerr << n << " : " << lim << '\n';
for(int i = 0; i < min(n,lim); i++)
{
vi q = query(i);
if(q[0] + q[1] == 0)
return i;
}
// lim = 1; //the first thing must be a lollipop
for(int i = 0; i < lim; i++)
{
vi qi = query(i);
prizes = max(prizes, qi[0] + qi[1]);
}
// cerr << "prizes = " << prizes << '\n';
solve(lim, n-1);
for(int i = 0; i < n; i++)
if(!qr[i].empty())
if(qr[i][0] + qr[i][1] == 0)
return i;
// cerr << "critical error\n";
assert(0);
return -1;
}
