oj.uz

Submission #404699

# Submission time Handle Problem Language Result Execution time Memory
404699 2021-05-14T20:51:21 Z Jasiekstrz Hotter Colder (IOI10_hottercolder) C++17
92 / 100
 5595 ms 8480 KB 
#include<bits/stdc++.h>
#include "grader.h"
using namespace std;
set<int> st;
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;
	}
	st.clear();
	mt19937 gen(2913319);
	int bg=1,en=N;
	int l=-1;
	while(bg<en)
	{
		//cerr<<bg<<" "<<en<<" "<<l<<"\n";
		if(l<bg || en<l)
		{
			if(uniform_int_distribution<int>{0,1}(gen))
				l=bg;
			else
				l=en;
			Guess(l);
		}
		if(l==bg)
		{
			int nl=en-max(0,(en-bg)/3-1);
			if((nl+l)%2==1 && nl-1>l)
				nl--;
			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+max(0,(en-bg)/3-1);
			if((nl+l)%2==1 && nl+1<l)
				nl++;
			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-bg>=en-l)
		{
			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;
				st.insert(nl);
			}
			l=nl;
		}
		else
		{
			int nl=l+1;
			int tmp=Guess(nl);
			if(tmp==0)
				return (nl+l)/2;
			else if(tmp==1)
				bg=nl;
			//else if(bg==nl || en-l<=1)
			//	bg=l;
			else
			{
				en=nl;
				st.insert(nl);
			}
			l=nl;
		}
		while(l!=bg && !st.empty() && bg==(*st.begin()))
		{
			bg++;
			st.erase(st.begin());
		}
		while(l!=en && !st.empty() && en==(*prev(st.end())))
		{
			en--;
			st.erase(prev(st.end()));
		}
	}
	return bg;
}

Subtask #1
25.0 / 25.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 578 ms 1288 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 577 ms 1288 KB Output is correct

Subtask #4
17.0 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 5595 ms 8480 KB Output is partially correct - alpha = 0.666666666667