oj.uz

Submission #404612

# Submission time Handle Problem Language Result Execution time Memory
404612 2021-05-14T17:57:36 Z Jasiekstrz Hotter Colder (IOI10_hottercolder) C++17
85 / 100
 5150 ms 8552 KB 
#include<bits/stdc++.h>
#include "grader.h"
using namespace std;
bool go_lg(int &bg,int &en,int &tmp)
{
	if(tmp==0)
		return true;
	else if(tmp==-1)
		en=(bg+en-1)/2;
	else
		bg=(bg+en+2)/2;
	return false;
}
bool go_gl(int &bg,int &en,int &tmp)
{
	if(tmp==0)
		return true;
	else if(tmp==1)
		en=(bg+en-1)/2;
	else
		bg=(bg+en+2)/2;
	return false;
}
int HC(int N)
{
	if(N==1)
		return 1;
	if(N==2)
	{
		Guess(1);
		int tmp=Guess(2);
		if(tmp==1)
			return 2;
		return 1;
	}
	mt19937 gen(2913319);
	int bg=1,en=N;
	int l=-1;
	while(bg<en)
	{
		//cerr<<bg<<" "<<en<<" "<<l<<"\n";
		if(l==bg)
		{
			int nl=en;
			int tmp=Guess(nl);
			if(go_lg(bg,en,tmp))
				return (bg+en)/2;
			l=nl;
		}
		else if(l==en)
		{
			int nl=bg;
			int tmp=Guess(nl);
			if(go_gl(bg,en,tmp))
				return (bg+en)/2;
			l=nl;
		}
		else
		{
			l=(bg+en-1)/2;
			int nl=(bg+en+2)/2;
			if(uniform_int_distribution<int>{0,1}(gen))
			{
				Guess(nl);
				int tmp=Guess(l);
				if(tmp==0)
					return (bg+en)/2;
				else if(tmp==1)
					en=l;
				else if((en-bg+1)<4)
					bg=nl;
				else
					bg=l;
			}
			else
			{
				Guess(l);
				int tmp=Guess(nl);
				if(tmp==0)
					return (bg+en)/2;
				else if(tmp==1)
					bg=nl;
				else if((en-bg+1)<4)
					en=l;
				else
					en=nl;
				l=nl;
			}
		}
	}
	return bg;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 607 ms 1276 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 586 ms 1276 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 585 ms 1280 KB Output is correct

Subtask #4
10.0 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 5150 ms 8552 KB Output is partially correct - alpha = 0.400000000000