#include "grader.h"
bool initialized = false;
long long int hcdp[50];
void init() {
initialized = true;
hcdp[0] = 1;
hcdp[1] = 1;
hcdp[2] = 3;
hcdp[3] = 5;
for (int i = 4; i < 40; i++) {
hcdp[i] = hcdp[i - 2] + (1LL << (i - 1));
//printf("dp%d %lld\n", i, hcdp[i]);
}
}
int find(int start, int end, int lastguess) {
while (1) {
if (start > end)return start;
if (start == end)return start;
int curguess = start + end - lastguess;
if ((start + end) % 2 == 1) {
if (curguess > (start + end) / 2) {
curguess++;
}
else {
curguess--;
}
}
if (curguess == lastguess) {
curguess++;
}
int gres = Guess(curguess);
if (gres == 0)return (curguess + lastguess) / 2;
if ((gres<0 && curguess>lastguess) || (gres > 0 && curguess < lastguess)) {
end = (curguess + lastguess + 1) / 2 - 1;
}
else {
start = (curguess + lastguess) / 2 + 1;
}
lastguess = curguess;
}
}
int HC(int N) {
if (!initialized) {
init();
}
if (N == 1)return 1;
if (N <= 3) {
Guess(1);
int cres = Guess(N);
if (cres == 1)return N;
if (cres == -1)return 1;
return 2;
}
int mid = (2 + N) / 2;
int gleft = 0;
int initsize = mid / 2;
for (int i = 0;; i++) {
if ((1LL << i) > N * 3 - 2)break;
gleft = i;
}
gleft -= 3;
//printf("N %d GL %d mid %d initsize %d\n", N, gleft, mid, initsize);
int fg = Guess(mid - 2);
int sg = Guess(mid);
int lastguess = mid;
if (sg == 0)return mid - 1;
if (sg < 0) {
// 1 ~ mid-2
lastguess = 1;
int cres = Guess(1);
int rs = 1;
int re = mid;
if (cres == 0) {
return (1 + mid) / 2;
}
else if (cres < 0) {
rs = (1 + mid) / 2 + 1;
}
else {
re = mid / 2;
}
//printf("a b %d %d\n", rs, re);
if (rs == re)return rs;
if (gleft <= 1 && rs == 1) {
cres = Guess(3);
return cres + 2;
}
else if (gleft == 2 && rs == 1) {
cres = Guess(3);
if (cres < 1)return cres + 2;
cres = Guess(5);
return cres + 4;
}
int nextg = hcdp[gleft - 1] * 2 + rs * 2 - 1;
if (nextg + re - rs >= N)nextg = N - re + rs;
while (rs != re) {
gleft--;
cres = Guess(nextg);
if (cres == 0)return (1 + nextg) / 2;
if (cres < 0) {
re = nextg / 2;
}
else {
rs = (1 + nextg) / 2 + 1;
return find(rs, re, nextg);
}
lastguess = nextg;
if (rs == re)return rs;
gleft--;
Guess(rs);
if (rs > 1)return find(rs, re, rs);
if (gleft <= 1 && rs == 1) {
cres = Guess(3);
return cres + 2;
}
else if (gleft == 2 && rs == 1) {
cres = Guess(3);
if (cres < 1)return cres + 2;
cres = Guess(5);
return cres + 4;
}
nextg = hcdp[gleft - 1] * 2 + rs * 2 - 1;
if (nextg + re - rs >= N)nextg = N - re + rs;
}
return rs;
}
else {
// mid ~ end
lastguess = N;
int cres = Guess(N);
int rs = mid;
int re = N;
if (cres == 0) {
return (N + mid) / 2;
}
else if (cres < 0) {
re = (mid + N + 1) / 2 - 1;
}
else {
rs = (N + mid) / 2 + 1;
}
//printf("a b %d %d\n", rs, re);
if (rs == re)return rs;
if (gleft <= 1 && re == N) {
cres = Guess(N - 2);
return N - 1 - cres;
}
else if (gleft == 2 && re == N) {
cres = Guess(N - 2);
if (cres < 1)return N - 1 - cres;
cres = Guess(N - 4);
return N - 3 - cres;
}
int nextg = N - (hcdp[gleft - 1] * 2) + (re - N) * 2;
if (nextg - re + rs < 1)nextg = 1 + re - rs;
while (rs != re) {
gleft--;
cres = Guess(nextg);
if (cres == 0)return (N + nextg) / 2;
if (cres < 0) {
rs = (N + nextg) / 2 + 1;
}
else {
re = (nextg + N + 1) / 2 - 1;
return find(rs, re, nextg);
}
lastguess = nextg;
if (rs == re)return rs;
gleft--;
Guess(re);
if (re < N)return find(rs, re, re);
if (gleft <= 1 && re == N) {
cres = Guess(N - 2);
return N - 1 - cres;
}
else if (gleft == 2 && re == N) {
cres = Guess(N - 2);
if (cres < 1)return N - 1 - cres;
cres = Guess(N - 4);
return N - 3 - cres;
}
nextg = N - (hcdp[gleft - 1] * 2) + (N - re) * 2;
if (nextg - re + rs < 1)nextg = 1 + re - rs;
}
return rs;
}
}
