#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
int n;
int search(int lo, int hi, int prev_guess)
{
if (lo == hi)
return lo;
if (lo + 1 == hi)
{
Guess(lo);
if (Guess(hi) > 1)
return hi;
return lo;
}
if (lo + 2 == hi)
{
Guess((lo + hi) / 2);
if (Guess(lo) > 1)
return lo;
if (Guess(hi) > 1)
return hi;
return (lo + hi) / 2;
}
// we know that the previous guess was 'prev_guess',
// so our next guess can maybe always cut the search space in two?
int next_guess = lo + hi - prev_guess;
if (next_guess < 1 || n < next_guess)
{
Guess(lo);
prev_guess = lo;
next_guess = hi;
}
int result = Guess(next_guess);
int m1 = (prev_guess + next_guess) / 2;
int m2 = (prev_guess + next_guess + 1) / 2;
if (result == 0)
return m1;
if ((next_guess < prev_guess && result < 0) || (prev_guess < next_guess && result > 0))
return search(max(lo, m2), hi, next_guess);
return search(lo, min(hi, m1), next_guess);
}
int HC(int N)
{
n = N;
Guess((2 + N) / 3);
return search(1, N, 1);
}
