#include "prize.h"
#include <vector>
#include <iostream>
using namespace std;
typedef vector<int> vi;
// There is 1 diamond
// There is n - 1 lollipops.
int find_best(int n)
{
// Binary Search
// Highest is the highest box THAT IT COULD BE IN. Same for lowest
int highest = n - 1;
int lowest = 0;
while (highest != lowest)
{
int current = (highest + lowest) / 2;
vi answer = ask(current);
// cout << "Current: " << current << " - Range: (" << lowest << ", " << highest << ") - Query: [" << answer[0] << ", " << answer[1] << "]" << endl;
if (answer[0] == answer[1] && answer[0] == 0)
{
// cout << "Here" << endl;
// This is it
highest = current;
lowest = current;
}
if (answer[0] == 1)
{
highest = current;
}
else if (answer[1] == 1)
{
lowest = current;
}
}
return lowest;
// for(int i = 0; i < n; i++) {
// std::vector<int> res = ask(i);
// if(res[0] + res[1] == 0)
// return i;
// }
// return 0;
}
// n boxes (0 to n - 1)
// each with a prize
// v types of prize
// numbered from 1 to b in decreasing order of value
// Prize 1 - Diamond (exactly 1)
// Prize v - lollipop.
// Number of cheaper is much larger than numbe rof expeonsive ones/
// For all t, if there is k types of prize for t - 1, then theres > k^2 prizes of type t.
// You want to win the diamond.
// At the end of the game, you open a box and get the prize
// Before choosing a box, you get to ask Rambox, the host, some questions.
// For eahc question, you choose some box i
// He will answer with an array a containing two integers:
// 1. to the left of box i there are a[0] boxes with a more expensive prize
// 2 To the right of i there are exactly a[1] boxes with a more expensive prize than in box i.
