Submission #760100

#	Time	Username	Problem	Language	Result	Execution time	Memory
760100		SanguineChameleon	Hotter Colder (IOI10_hottercolder)	C++17	80 / 100	686 ms	24364 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) {
		swap(lt, rt);
	}
	while (lt < rt) {
		int res = -2;
		if (prv == lt) {
			res = Guess(rt);
			prv = rt;
		}
		else if (prv == rt) {
			res = -Guess(lt);
			prv = lt;
		}
		else if (dist(gen) == 0) {
			Guess(lt);
			res = Guess(rt);
			prv = rt;
		}
		else {
			Guess(rt);
			res = -Guess(lt);
			prv = lt;
		}
		if (res == 0) {
			return (lt + rt) / 2;
		}
		if (res == 1) {
			lt = (lt + rt) / 2 + 1;
		}
		else {
			rt = (lt + rt - 1) / 2;
		}
	}
	return lt;
}

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: 5 / 25