Submission #410407

#	Time	Username	Problem	Language	Result	Execution time	Memory
410407		rainboy	Hotter Colder (IOI10_hottercolder)	C11	100 / 100	643 ms	24392 KiB

hottercolder

/* https://ioi2010.org/competitiontask/day1/hottercolder/index.html */
#include "grader.h"

#define K	30

int n, flip;

int guess(int x) {
	return Guess(flip ? n + 1 - x : x);
}

int nn[K];

void init() {
	int i;

	nn[0] = 1, nn[1] = 3, nn[2] = 7;
	for (i = 3; i < K; i++)
		nn[i] = nn[i - 2] + (1 << i);
}

int search(int lower, int upper, int x) {
	while (lower < upper) {
		int g = guess(x = lower + upper - x);

		if (g == 0)
			return (lower + upper) / 2;
		if ((lower + upper - x < x) == (g > 0))
			lower = (lower + upper) / 2 + 1;
		else
			upper = (lower + upper + 1) / 2 - 1;
	}
	return lower;
}

int search_(int n, int k) {
	int g, x;

	if (n == 1)
		return 1;
	else if (n <= 3) {
		g = guess(1);
		return g == 0 ? 2 : (g > 0 ? 1 : n);
	} else if (n <= 5) {
		g = guess(n - 2);
		if (g < 0)
			return n;
		if (g == 0)
			return n - 1;
		g = guess(1);
		return g == 0 ? 2 : (g > 0 ? 1 : n - 2);
	} else if (n <= 7) {
		g = guess(1);
		if (g > 0) {
			g = guess(3);
			return g == 0 ? 2 : (g > 0 ? 3 : 1);
		} else if (g < 0) {
			g = guess((n - 1) * 2 - 1);
			return g == 0 ? n - 1 : (g > 0 ? n : n - 2);
		} else
			return 4;
	}
	if (n <= nn[k - 2])
		return search_(n, k - 2);
	g = guess(nn[k - 2] - 2);
	if (g < 0) {
		x = (nn[k - 2] - 2 + n) / 2 + 2;
		g = guess(x * 2 - (nn[k - 2] - 2));
		if (g == 0)
			return x;
		else if (g < 0)
			return x - 1;
		else
			return search(x + 1, n, x * 2 - (nn[k - 2] - 2));
	} else if (g > 0) {
		g = guess(nn[k - 2]);
		if (g < 0)
			return search_(nn[k - 2], k - 2);
		else if (g > 0)
			return search(nn[k - 2], (nn[k - 2] - 2 + n + 1) / 2 - 1, nn[k - 2]);
		else
			return nn[k - 2] - 1;
	} else
		return (nn[k - 2] - 2 + n) / 2;
}

int HC(int N) {
	int g, k;

	n = N;
	if (!nn[0])
		init();
	if (n == 1)
		return 1;
	else if (n == 2) {
		Guess(1);
		return Guess(2) < 0 ? 1 : 2;
	} else if (n == 3) {
		Guess(1), g = Guess(3);
		return g == 0 ? 2 : (g < 0 ? 1 : 3);
	} else {
		Guess(n / 2), g = Guess(n / 2 + 1);
		if (g < 0) {
			k = 0;
			while (nn[k] < n / 2 + 1)
				k++;
			flip = 0;
			return search_(n / 2 + 1, k);
		} else {
			k = 0;
			while (nn[k] < n - n / 2)
				k++;
			flip = 1;
			return n + 1 - search_(n - n / 2, k);
		}
	}
}

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