Submission #404689

#	Time	Username	Problem	Language	Result	Execution time	Memory
404689		Jasiekstrz	Hotter Colder (IOI10_hottercolder)	C++17	87 / 100	608 ms	10856 KiB

hottercolder

#include<bits/stdc++.h>
#include "grader.h"
using namespace std;
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 || en<l)
		{
			l=bg;
			Guess(l);
		}
		if(l==bg)
		{
			int nl=en-(en-bg)/3;
			int tmp=Guess(nl);
			if(tmp==0)
				return (nl+l)/2;
			else if(tmp==-1)
				en=(nl+l-1)/2;
			else
				bg=(nl+l+2)/2;
			l=nl;
		}
		else if(l==en)
		{
			int nl=bg+(en-bg)/3;
			int tmp=Guess(nl);
			if(tmp==0)
				return (nl+l)/2;
			else if(tmp==1)
				en=(nl+l-1)/2;
			else
				bg=(nl+l+2)/2;
			l=nl;
		}
		else
		{
			int nl=l-1;
			int tmp=Guess(nl);
			if(tmp==0)
				return (nl+l)/2;
			else if(tmp==1)
				en=nl;
			//else if(bg==nl || en-l<=1)
			//	bg=l;
			else
				bg=nl;
			l=nl;
		}
	}
	return bg;
}

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