답안 #410407

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
410407 2021-05-22T16:10:52 Z rainboy Hotter Colder (IOI10_hottercolder) C
100 / 100
643 ms 24392 KB
/* 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);
		}
	}
}
# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 1336 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 1280 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 1228 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Partially correct 643 ms 24392 KB Output is partially correct - alpha = 1.000000000000