#include "grader.h"
#include <algorithm>
using namespace std;
// hcdp[i] stores the maximum range size solvable with i guesses remaining.
long long hcdp[50];
bool is_initialized = false;
/**
* Pre-calculates the maximum solvable ranges using the DP recurrence.
* The recurrence hcdp[i] = hcdp[i-2] + 2^(i-1) defines the strategy's reach.
*/
void initialize_dp() {
is_initialized = true;
hcdp[0] = 1;
hcdp[1] = 1;
hcdp[2] = 3;
hcdp[3] = 5;
for (int i = 4; i < 45; i++) {
hcdp[i] = hcdp[i - 2] + (1LL << (i - 1));
}
}
/**
* Standard Mirror Search:
* Narrows down the range [start, end] using the 'last_guess' as a pivot.
* Targets the midpoint of the current range for the next boundary.
*/
int mirror_search(int start, int end, int last_guess) {
while (start < end) {
int next_guess = start + end - last_guess;
// Adjust for parity to ensure the boundary falls correctly
if ((start + end) % 2 == 1) {
if (next_guess > (start + end) / 2) next_guess++;
else next_guess--;
}
// Avoid repeating the same guess
if (next_guess == last_guess) {
next_guess = (last_guess < end) ? last_guess + 1 : last_guess - 1;
}
int result = Guess(next_guess);
if (result == 0) return (next_guess + last_guess) / 2;
// If 'Colder' while moving up, or 'Hotter' while moving down,
// the target is in the lower half.
if ((result < 0 && next_guess > last_guess) || (result > 0 && next_guess < last_guess)) {
end = (next_guess + last_guess + 1) / 2 - 1;
} else {
start = (next_guess + last_guess) / 2 + 1;
}
last_guess = next_guess;
}
return start;
}
int HC(int N) {
if (!is_initialized) initialize_dp();
if (N == 1) return 1;
// Base case for small N to save initial queries
if (N <= 3) {
Guess(1);
int res = Guess(N);
return (res == 1) ? N : (res == -1 ? 1 : 2);
}
// Determine total guesses available based on N
int guesses_left = 0;
while ((1LL << guesses_left) > N * 3 - 2 == false) guesses_left++;
guesses_left -= 3;
int mid = (2 + N) / 2;
Guess(mid - 2);
int second_guess = Guess(mid);
if (second_guess == 0) return mid - 1;
int range_start, range_end, last_guess;
if (second_guess < 0) { // Target is in the lower half: [1, mid-2]
last_guess = 1;
int res = Guess(1);
range_start = 1;
range_end = mid;
if (res == 0) return (1 + mid) / 2;
if (res < 0) range_start = (1 + mid) / 2 + 1;
else range_end = mid / 2;
if (range_start == range_end) return range_start;
// Handle edge cases for low remaining guesses
if (guesses_left <= 2 && range_start == 1) {
int final_res = Guess(3);
if (guesses_left == 2 && final_res == 1) return Guess(5) + 4;
return final_res + 2;
}
// DP-guided search loop
while (range_start != range_end) {
guesses_left--;
int next_target = hcdp[guesses_left - 1] * 2 + range_start * 2 - 1;
if (next_target + range_end - range_start >= N)
next_target = N - range_end + range_start;
int res_loop = Guess(next_target);
if (res_loop == 0) return (1 + next_target) / 2;
if (res_loop < 0) {
range_end = next_target / 2;
if (range_start == range_end) return range_start;
guesses_left--;
Guess(range_start);
if (range_start > 1) return mirror_search(range_start, range_end, range_start);
} else {
range_start = (1 + next_target) / 2 + 1;
return mirror_search(range_start, range_end, next_target);
}
}
return range_start;
} else { // Target is in the upper half: [mid, N]
last_guess = N;
int res = Guess(N);
range_start = mid;
range_end = N;
if (res == 0) return (N + mid) / 2;
if (res < 0) range_end = (mid + N + 1) / 2 - 1;
else range_start = (N + mid) / 2 + 1;
if (range_start == range_end) return range_start;
// DP-guided search loop for the upper bound
while (range_start != range_end) {
guesses_left--;
int next_target = N - (hcdp[guesses_left - 1] * 2) + (range_end - N) * 2;
if (next_target - range_end + range_start < 1)
next_target = 1 + range_end - range_start;
int res_loop = Guess(next_target);
if (res_loop == 0) return (N + next_target) / 2;
if (res_loop < 0) {
range_start = (N + next_target) / 2 + 1;
if (range_start == range_end) return range_start;
guesses_left--;
Guess(range_end);
if (range_end < N) return mirror_search(range_start, range_end, range_end);
} else {
range_end = (next_target + N + 1) / 2 - 1;
return mirror_search(range_start, range_end, next_target);
}
}
return range_start;
}
}
