#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;
vector<int> r = ask(N - 1);
if(r[0] + r[1] < maxi)
{
estUtile[N - 1] = true;
}
dejaVu[N - 1] = true;
resultGauche[N - 1] = r[0];
while(curCadeau < N)
{
if(estUtile[curCadeau])
{
curCadeau++;
continue;
}
vector<int> r;
int nbGauche;
if(dejaVu[curCadeau])
{
nbGauche = resultGauche[curCadeau];
}
else
{
r = ask(curCadeau);
if(r[0] + r[1] < maxi)
{
estUtile[curCadeau] = true;
curCadeau++;
continue;
}
dejaVu[curCadeau] = true;
resultGauche[curCadeau] = r[0];
nbGauche = r[0];
}
int borneGauche = curCadeau, borneDroite = N - 1;
while(borneGauche < borneDroite - 1)
{
//cout << borneGauche << " " << borneDroite << endl;
int mid = (borneGauche + borneDroite) / 2;
if(estUtile[mid])
{
borneDroite = mid;
}
else if(dejaVu[mid])
{
if(resultGauche[mid] == nbGauche)
{
borneGauche = mid;
}
else
{
borneDroite = mid;
}
}
else
{
r = ask(mid);
dejaVu[mid] = true;
resultGauche[mid] = r[0];
if(r[0] + r[1] < maxi)
{
estUtile[mid] = true;
borneDroite = mid;
}
else if(r[0] > nbGauche)
{
borneDroite = mid;
}
else
{
borneGauche = mid;
}
}
}
//cout << borneGauche << " " << borneDroite << endl;
if(!estUtile[borneDroite] && resultGauche[borneDroite] == nbGauche)
{
curCadeau = borneDroite + 1;
}
else
{
curCadeau = borneGauche + 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;
}
