Submission #748834

#	Time	Username	Problem	Language	Result	Execution time	Memory
748834		wenqi	Hotter Colder (IOI10_hottercolder)	C++17	50 / 100	546 ms	8188 KiB

hottercolder

#include "grader.h"
#include <algorithm>
#include <iostream>
using namespace std;

int R(int, int);

int L(int l, int r)
{
	if (l == r)
		return l;
	int g = Guess(r);
	if (g == 0)
	{
		return (l + r) / 2;
	}
	if (g == 1)
	{
		return R((l + r) / 2 + 1, r);
	}
	Guess(l);
	return L(l, (l + r - 1) / 2);
}

int R(int l, int r)
{
	if (l == r)
		return l;
	int g = Guess(l);
	if (g == 0)
	{
		return (l + r) / 2;
	}
	if (g == 1)
	{
		return L(l, (l + r - 1) / 2);
	}
	Guess(r);
	return R((l + r) / 2 + 1, r);
}

int N;

int search(int l, int r, int q)
{
	if (l == r)
		return l;
	int m = (l + r) / 2;
	int w = l + r - q;
	w = clamp(w, 1, N);
	// printf("%d %d %d %d\n", l, r, q, w);
	m = (w + q) / 2;
	int g = Guess(w);
	if (2 * q < l + r)
	{
		if (g == 0)
			return m;
		if (g == 1)
			return search(m + 1, r, w);
		return search(l, m, w);
	}
	if (g == 0)
		return m;
	if (g == -1)
		return search(m + 1, r, w);
	return search(l, m, w);
}

int HC(int N_)
{
	N = N_;
	Guess(1);
	// int guess = L(1, N);
	int guess = search(1, N, 1);
	return guess;
}

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