oj.uz

Submission #119564

# Submission time Handle Problem Language Result Execution time Memory
119564 2019-06-21T11:47:21 Z WhipppedCream Hotter Colder (IOI10_hottercolder) C++17
79 / 100
 839 ms 8312 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 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.0 / 25.0

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

Subtask #2
25.0 / 25.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 1268 KB Output is correct

Subtask #4
4.0 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 839 ms 8312 KB Output is partially correct - alpha = 0.166666666667