oj.uz

Submission #119571

# Submission time Handle Problem Language Result Execution time Memory
119571 2019-06-21T11:55:40 Z WhipppedCream Hotter Colder (IOI10_hottercolder) C++17
83 / 100
 2505 ms 8184 KB 
#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

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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 1272 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 1400 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 1400 KB Output is correct

Subtask #4
8.0 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 2505 ms 8184 KB Output is partially correct - alpha = 0.333333333333