Submission #760136

#	Time	Username	Problem	Language	Result	Execution time	Memory
760136		SanguineChameleon	Hotter Colder (IOI10_hottercolder)	C++17	100 / 100	629 ms	8108 KiB

hottercolder

#include "grader.h"
#include <bits/stdc++.h>
using namespace std;

int N;

int fix(int dir, int X) {
	return (dir == 1 ? X : N + 1 - X);
}

mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<int> dist(0, 1);
int max_end[30];

int mid_game(int lt, int rt, int prv) {
	if (lt == rt) {
		return lt;
	}
	if (lt > rt) {
		swap(lt, rt);
	}
	int len = 1;
	while (len < rt - lt + 1) {
		len = len * 2 + 1;
	}
	int mt = -1;
	if (prv < rt - len + 1) {
		mt = rt - len / 2;
	}
	else if (prv > lt + len - 1) {
		mt = lt + len / 2;
	}
	else if (prv <= lt) {
		mt = prv + len / 2;
	}
	else {
		mt = prv - len / 2;
	}
	int nxt = mt * 2 - prv;
	int res = Guess(nxt);
	if (res == 0) {
		return mt;
	}
	else if ((prv < nxt && res < 0) || (prv > nxt && res > 0)) {
		return mid_game(lt, mt - 1, nxt);
	}
	else {
		return mid_game(mt + 1, rt, nxt);
	}
}

int end_game(int dir, int len) {
	if (len == 2) {
		int res = Guess(fix(dir, 1));
		if (res > 0) {
			return fix(dir, 1);
		}
		else {
			return fix(dir, 2);
		}
	}
	if (len == 3) {
		int res = Guess(fix(dir, 1));
		if (res > 0) {
			return fix(dir, 1);
		}
		else if (res < 0) {
			return fix(dir, 3);
		}
		else {
			return fix(dir, 2);
		}
	}
	if (len == 4) {
		int res = Guess(fix(dir, 2));
		if (res > 0) {
			res = Guess(fix(dir, 1));
			if (res > 0) {
				return fix(dir, 1);
			}
			else {
				return fix(dir, 2);
			}
		}
		else if (res < 0) {
			return fix(dir, 4);
		}
		else {
			return fix(dir, 3);
		}
	}
	if (len == 5) {
		int res = Guess(fix(dir, 3));
		if (res > 0) {
			res = Guess(fix(dir, 1));
			if (res > 0) {
				return fix(dir, 1);
			}
			else if (res < 0) {
				return fix(dir, 3);
			}
			else {
				return fix(dir, 2);
			}
		}
		else if (res < 0) {
			return fix(dir, 5);
		}
		else {
			return fix(dir, 4);
		}
	}
	if (len == 6) {
		int res = Guess(fix(dir, 1));
		if (res > 0) {
			res = Guess(fix(dir, 3));
			if (res > 0) {
				return fix(dir, 3);
			}
			else if (res < 0) {
				return fix(dir, 1);
			}
			else {
				return fix(dir, 2);
			}
		}
		else {
			res = Guess(fix(dir, 9));
			if (res > 0) {
				return fix(dir, 6);
			}
			else if (res < 0) {
				return fix(dir, 4);
			}
			else {
				return fix(dir, 5);
			}
		}
	}
	if (len == 7) {
		int res = Guess(fix(dir, 1));
		if (res > 0) {
			res = Guess(fix(dir, 3));
			if (res > 0) {
				return fix(dir, 3);
			}
			else if (res < 0) {
				return fix(dir, 1);
			}
			else {
				return fix(dir, 2);
			}
		}
		else if (res < 0) {
			res = Guess(fix(dir, 11));
			if (res > 0) {
				return fix(dir, 7);
			}
			else if (res < 0) {
				return fix(dir, 5);
			}
			else {
				return fix(dir, 6);
			}
		}
		else {
			return fix(dir, 4);
		}
	}
	int k = 3;
	while (max_end[k] < len) {
		k++;
	}
	int sum = len + max_end[k - 2] - 2;
	int res = Guess(fix(dir, max_end[k - 2] - 2));
	if (res < 0) {
		return mid_game(fix(dir, sum / 2 + 1), fix(dir, len), fix(dir, max_end[k - 2] - 2));
	}
	else if (res > 0) {
		len = (sum - 1) / 2;
		res = Guess(fix(dir, max_end[k - 2]));
		if (res < 0) {
			return end_game(dir, max_end[k - 2]);
		}
		else if (res > 0) {
			return mid_game(fix(dir, max_end[k - 2]), fix(dir, (sum - 1) / 2), fix(dir, max_end[k - 2]));
		}
		else {
			return fix(dir, max_end[k - 2] - 1);
		}
	}
	else {
		return fix(dir, sum / 2);
	}
}

int HC(int _N) {
	max_end[1] = 3;
	max_end[2] = 7;
	for (int i = 3; i < 30; i++) {
		max_end[i] = max_end[i - 2] + (1 << i);
	}
	N = _N;
	if (N == 1) {
		return 1;
	}
	if (N == 2) {
		Guess(1);
		int res = Guess(2);
		if (res > 0) {
			return 2;
		}
		else {
			return 1;
		}
	}
	if (N == 3) {
		Guess(1);
		int res = Guess(3);
		if (res > 0) {
			return 3;
		}
		else if (res < 0) {
			return 1;
		}
		else {
			return 2;
		}
	}
	int mid = (N + 2) / 2;
	Guess(mid - 2);
	int res = Guess(mid);
	if (res < 0) {
		return end_game(1, mid);
	}
	else if (res > 0) {
		return end_game(-1, N - mid + 1);
	}
	else {
		return mid - 1;
	}
}

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