#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500;
vector<pair<int, int> > values(200001, {-1, -1});
int 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;
if(ischecked[mid] != 0)
{
return ischecked[mid];
}
vector<int> current_reply(2);
if(values[mid].first == -1)
{
current_reply = ask(mid);
values[mid] = {current_reply[0], current_reply[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 << endl;
// values[mid] = {current_reply[0], current_reply[1]};
current_reply = {values[mid].first, values[mid].second};
if(current_reply[0] + current_reply[1] == 0)
{
// cout << "found diamond" << endl;
return ischecked[mid] = mid;
}
// if(parent_left + parent_right != current_reply[0] + current_reply[1])
// {
// // higher to lower or vice versa, don't do anything based on 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)
// {
// int value = DivideAndConquer(mid + 1, r, mid, current_reply[0], current_reply[1]);
// if(value != -1) // value found
// {
// return value;
// }
// }
// return -1; // value not found in both children
// }
// 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 == N)
{
if(current_reply[0] != 0)
{
int value = DivideAndConquer(l, mid - 1, mid, current_reply[0], current_reply[1]);
if(value != -1)
{
return ischecked[mid] = value;
}
}
if(current_reply[1] != 0)
{
int value = DivideAndConquer(mid + 1, r, mid, current_reply[0], current_reply[1]);
if(value != -1)
{
return ischecked[mid] = value;
}
}
return ischecked[mid] = -1;
}
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 ischecked[mid] = 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 ischecked[mid] = value;
}
}
return ischecked[mid] = -1;
}
else
{
if(current_reply[1] != 0)
{
int value = DivideAndConquer(mid + 1, r, mid, current_reply[0], current_reply[1]);
if(value != -1) // value found
{
return ischecked[mid] = value;
}
}
if(current_reply[0] != 0 && current_reply[1] != parent_right)
{
int value = DivideAndConquer(l, mid - 1, mid, current_reply[0], current_reply[1]);
if(value != -1) // value found
{
return ischecked[mid] = value;
}
}
return ischecked[mid] = -1;
}
}
int find_best(int n)
{
N = n;
for(int i = 0; i < min(n, MAXN); i++)
{
vector<int> reply = ask(i);
values[i] = {reply[0], reply[1]};
best_sum = max(best_sum, reply[0] + reply[1]);
}
// 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);
}
