Submission #119571

#	Time	Username	Problem	Language	Result	Execution time	Memory
119571		WhipppedCream	Hotter Colder (IOI10_hottercolder)	C++17	83 / 100	2505 ms	8184 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 n;

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
	{
		int mid = (a+b)/2;
		if(last> b)
		{
			int dx = last-b;
			if(1<= a-dx)
			{
				int res = Guess(a-dx);
				if((a+b)%2 == 1)
				{
					assert(res);
					if(res == 1) return solve(a, mid, a-dx);
					return solve(mid+1, b, a-dx);
				}
				else
				{
					if(res == 0) return mid;
					if(res == 1) return solve(a, mid-1, a-dx);
					return solve(mid+1, b, a-dx);
				}
			}
		}
		else if(last< a)
		{
			int dx = a-last;
			if(b+dx<= n)
			{
				int res = Guess(b+dx);
				if((a+b)%2 == 1)
				{
					assert(res);
					if(res == 1) return solve(mid+1, b, b+dx);
					return solve(a, mid, b+dx);
				}
				else
				{
					if(res == 0) return mid;
					if(res == 1) return solve(mid+1, b, b+dx);
					return solve(a, mid-1, b+dx);
				}
			}
		}
		int x = rand()%2;
		if(x)
		{
			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);
			}
		}
		else
		{
			Guess(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);
			}
		}
	}
}

int HC(int N)
{
	srand(time(NULL));
	n = N;
	return solve(1, N, -1);
}

Compilation message (stderr)

hottercolder.cpp: In function 'int HC(int)':
hottercolder.cpp:111:4: warning: assuming signed overflow does not occur when assuming that (X + c) < X is always false [-Wstrict-overflow]
    if(b+dx<= n)
    ^~

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