#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 450;
vector<pair<int, int> > values(200001, {-1, -1});
bool ischecked[200001];
int N, best_sum = 0;
bool cmp(array<int, 3> a, array<int, 3> b)
{
return ((a[0] + a[1]) > (b[0] + b[1]));
}
int DivideAndConquer(int l, int r, int parent_value, int parent_left, int parent_right) // index of diamond (-1 if not found)
{
// cout << "l = " << l << ", r = " << r << ", parent_value = " << parent_value << ", parent_left = " << parent_left << ", parent_right = " << parent_right << endl;
if(l > r)
{
return -1;
}
int mid = (l + r) >> 1;
vector<int> current_reply(2);
int cur_l = mid, cur_r = mid, cnt = 0;
while(cnt <= MAXN)
{
cnt++;
if(cnt % 2 == 1)
{
if(cur_l >= l && !ischecked[cur_l])
{
if(values[cur_l].first == -1)
{
current_reply = ask(cur_l);
values[cur_l] = {current_reply[0], current_reply[1]};
}
if(values[cur_l].first + values[cur_l].second == best_sum)
{
mid = cur_l;
break;
}
cur_l--;
}
}
else
{
if(cur_r < r && !ischecked[cur_r])
{
if(values[cur_r].first == -1)
{
current_reply = ask(cur_r);
values[cur_r] = {current_reply[0], current_reply[1]};
}
if(values[cur_r].first + values[cur_r].second == best_sum)
{
mid = cur_r;
break;
}
cur_r++;
}
}
}
// cout << "mid = " << mid << endl;
// cout << "l = " << l << ", r = " << r << ", mid = " << mid << "\n";
// values[mid] = {current_reply[0], current_reply[1]};
current_reply = {values[mid].first, values[mid].second};
ischecked[mid] = true;
if(current_reply[0] + current_reply[1] == 0)
{
return mid;
}
// equal value of parent and current
// if current is the left child of parent do:
// parent_left == current_left: No need to check right child
// else if current is the right child of parent do:
// parent_right == current_left: No ned to check right child
if(parent_value == r + 1) // current is the left child of parent
{
if(current_reply[0] != 0)
{
int value = DivideAndConquer(l, mid - 1, mid, current_reply[0], current_reply[1]);
if(value != -1) // value found
{
return value;
}
}
if(current_reply[1] != 0 && current_reply[0] != parent_left)
{
int value = DivideAndConquer(mid + 1, r, mid, current_reply[0], current_reply[1]);
if(value != -1) // value found
{
return value;
}
}
return -1;
}
else
{
if(current_reply[0] != 0)
{
int value = DivideAndConquer(l, mid - 1, mid, current_reply[0], current_reply[1]);
if(value != -1) // value found
{
return value;
}
}
if(current_reply[1] != 0 && current_reply[0] != parent_right)
{
int value = DivideAndConquer(mid + 1, r, mid, current_reply[0], current_reply[1]);
if(value != -1) // value found
{
return value;
}
}
return -1;
}
}
int find_best(int n)
{
int mid = n / 2 - 1;
N = n;
for(int i = mid - MAXN / 2; i <= mid + MAXN / 2; i++)
{
// cout << "i = " << i << "\n";
if(i < 0 || i > N)
{
continue;
}
vector<int> reply = ask(i);
values[i] = {reply[0], reply[1]};
best_sum = max(best_sum, reply[0] + reply[1]);
}
return DivideAndConquer(0, n - 1, n, 0, 0);
}
