#include "prize.h"
#include <iostream>
#include <vector>
#include <random>
#include <ctime>
using namespace std;
const int maxn = 200005;
int N;
int max_result = 0;
vector<int> results[maxn];
int divide(int l, int r, int removed_from_left, int removed_from_right)
{
if (l > r)
{
return 0;
}
int mid = (l + r) / 2;
vector<int> curr;
while (mid <= r)
{
//curr = ask(mid);
if (!results[mid].empty())
{
curr = results[mid];
}
else
{
curr = ask(mid);
results[mid].push_back(curr[0]);
results[mid].push_back(curr[1]);
}
if (curr[0] + curr[1] == 0)
{
return mid;
}
if (curr[0] + curr[1] == max_result)
{
break;
}
++mid;
}
if (mid <= r)
{
curr[0] -= (removed_from_left - (mid - (l + r) / 2));
curr[1] -= removed_from_right;
if (curr[0] > 0)
{
int idx = divide(l, (l + r) / 2 - 1, removed_from_left, removed_from_right + curr[1] + (mid - (l + r) / 2));
if (idx != 0)
{
return idx;
}
}
if (curr[1] > 0)
{
int idx = divide(mid + 1, r, removed_from_left + curr[0] + (mid - (l + r) / 2), removed_from_right);
if (idx != 0)
{
return idx;
}
}
return 0;
}
else
{
mid = (l + r) / 2 - 1;
while (mid >= l)
{
if (!results[mid].empty())
{
curr = results[mid];
}
else
{
curr = ask(mid);
results[mid].push_back(curr[0]);
results[mid].push_back(curr[1]);
}
if (curr[0] + curr[1] == 0)
{
return mid;
}
if (curr[0] + curr[1] == max_result)
{
return mid;
}
--mid;
}
if (mid == l - 1)
{
return 0;
}
curr[0] -= removed_from_left;
if (curr[0] > 0)
{
return divide(l, mid - 1, removed_from_left, removed_from_right + (r - mid));
}
return 0;
}
return 0;
}
int find_best(int n)
{
srand(time(NULL));
N = n;
for (int i = 0; i < min(n, 470); ++i)
{
int idx = rand() % n;
while (!results[idx].empty())
{
idx = rand() % n;
}
vector<int> curr_result = ask(idx);
results[idx].push_back(curr_result[0]);
results[idx].push_back(curr_result[1]);
max_result = max(max_result, curr_result[0] + curr_result[1]);
}
return divide(0, N - 1, 0, 0);
}
