#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500;
int find_best(int n)
{
vector<vector<int> > store(n + 1, vector<int> (2));
for(int i = 0; i <= n; i++)
{
store[i][0] = -1;
store[i][1] = -1;
}
int previous_optimal = -1;
store[0] = ask(0);
if(store[0][0] == 0 && store[0][1] == 0)
{
return 0;
}
int max_sum = store[0][0] + store[0][1];
for(int atleastbefore = 1; atleastbefore <= 200000; atleastbefore++)
{
int l = 0, r = n - 1;
int current_optimal = n - 1;
while(l < r)
{
int mid = (l + r) / 2;
// cout << "l = " << l << ", r = " << r << ", previous_optimal = " << previous_optimal << "\n";
if(mid <= previous_optimal)
{
l = mid + 1;
current_optimal = mid + 1;
continue;
}
if(store[mid][0] == -1)
{
store[mid] = ask(mid);
}
if(store[mid][0] + store[mid][1] == 0)
{
return mid;
}
if(store[mid][0] + store[mid][1] > max_sum)
{
max_sum = store[mid][0] + store[mid][1];
l = 0, r = n - 1;
continue;
}
if(store[mid][0] < atleastbefore && store[mid][0] + store[mid][1] == max_sum)
{
l = mid + 1;
current_optimal = mid + 1;
}
else
{
r = mid;
}
}
previous_optimal = current_optimal;
if(previous_optimal != 200000 && store[previous_optimal][0] == -1)
{
store[previous_optimal] = ask(previous_optimal);
}
if(previous_optimal != 200000 && store[previous_optimal][0] + store[previous_optimal][1] == 0)
{
return previous_optimal;
}
}
return -1;
}
