Submission #119564

#	Time	Username	Problem	Language	Result	Execution time	Memory
119564		WhipppedCream	Hotter Colder (IOI10_hottercolder)	C++17	79 / 100	839 ms	8312 KiB

hottercolder

#include <bits/stdc++.h>
#include "grader.h"
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;

int solve(int a, int b, int last)
{
	if(b-a+1 == 4)
	{
		Guess(a);
		int res = Guess(a+2);
		if(res == 0)
		{
			return a+1;
		}
		else if(res == -1)
		{
			return a;
		}
		else
		{
			int foo = Guess(a+3);
			if(foo == 1) return a+3;
			return a+2;
		}
	}
	if(b-a+1 == 3)
	{
		Guess(a);
		int res = Guess(a+2);
		if(res == 0) return a+1;
		if(res == 1) return a+2;
		return a;
	}
	if(b-a+1 == 2)
	{
		Guess(a);
		int res = Guess(a+1);
		if(res == 1) return a+1;
		return a;
	}
	if(a == b) return a;
	if(last == a)
	{
		int res = Guess(b);
		int mid = (a+b)/2;
		if((a+b)%2 == 1)
		{
			assert(res);
			if(res == 1) return solve(mid+1, b, b);
			return solve(a, mid, b);
		}
		else
		{
			if(res == 0) return mid;
			if(res == 1) return solve(mid+1, b, b);
			return solve(a, mid-1, b);
		}
	}
	else if(last == b)
	{
		int res = Guess(a);
		int mid = (a+b)/2;
		if((a+b)%2 == 1)
		{
			assert(res);
			if(res == 1) return solve(a, mid, a);
			return solve(mid+1, b, a);
		}
		else
		{
			if(res == 0) return mid;
			if(res == 1) return solve(a, mid-1, a);
			return solve(mid+1, b, a);
		}
	}
	else
	{
		Guess(a);
		int res = Guess(b);
		int mid = (a+b)/2;
		if((a+b)%2 == 1)
		{
			assert(res);
			if(res == 1) return solve(mid+1, b, b);
			return solve(a, mid, b);
		}
		else
		{
			if(res == 0) return mid;
			if(res == 1) return solve(mid+1, b, b);
			return solve(a, mid-1, b);
		}
	}
}

int HC(int N)
{
	return solve(1, N, -1);
}

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