Submission #1309637

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309637		gs12117	Hotter Colder (IOI10_hottercolder)	C++20	100 / 100	477 ms	8220 KiB

hottercolder

#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;
	}
}

• Subtask 1: 25 / 25
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 25 / 25