#include "prize.h"
#include <iostream>
using namespace std;
const int MAX_CADEAU = 2e5;
const int MAX_UTILE = 500;
bool estUtile[MAX_CADEAU];
bool dejaVu[MAX_CADEAU];
int resultGauche[MAX_CADEAU];
int find_best(int N)
{
int maxi = 0;
for(int iCadeau = 0; iCadeau < min(MAX_UTILE, N); iCadeau++)
{
vector<int> r = ask(iCadeau);
maxi = max(maxi, r[0] + r[1]);
}
int curCadeau = 0;
while(curCadeau < N)
{
//cout << curCadeau << endl;
if(estUtile[curCadeau])
{
curCadeau++;
continue;
}
vector<int> r = ask(curCadeau);
if(r[0] + r[1] < maxi)
{
estUtile[curCadeau] = true;
curCadeau++;
continue;
}
int nbGauche = r[0];
int borneDroite = N - 1;
while(curCadeau < borneDroite)
{
if(estUtile[borneDroite])
{
borneDroite--;
continue;
}
if(dejaVu[borneDroite] && resultGauche[borneDroite] == nbGauche)
{
break;
}
if(dejaVu[borneDroite] && resultGauche[borneDroite] > nbGauche)
{
borneDroite = (curCadeau + borneDroite) / 2;
continue;
}
r = ask(borneDroite);
dejaVu[borneDroite] = true;
resultGauche[borneDroite] = r[0];
if(r[0] + r[1] < maxi)
{
estUtile[borneDroite] = true;
borneDroite--;
continue;
}
if(r[0] == nbGauche)
{
break;
}
else
{
borneDroite = (curCadeau + borneDroite) / 2;
}
}
curCadeau = borneDroite + 1;
}
for(int curCadeau = 0; curCadeau < N; curCadeau++)
{
if(estUtile[curCadeau])
{
vector<int> r = ask(curCadeau);
if(r[0] + r[1] == 0)
{
return curCadeau;
}
}
}
return -1;
}
