oj.uz

Submission #138980

# Submission time Handle Problem Language Result Execution time Memory
138980 2019-07-31T05:53:49 Z baluteshih Hotter Colder (IOI10_hottercolder) C++14
87 / 100
 693 ms 8236 KB 
#include "grader.h"
#include <stdlib.h>
#include <stdio.h>
#include <chrono>
#define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pb push_back
#define ET cout << "\n"
#define F first
#define S second
#define MP make_pair
#define ALL(v) v.begin(),v.end()
#define MEM(i,j) memset(i,j,sizeof i)
#define DB(a,s,e) {for(int i=s;i<e;++i) cout << a[i] << " ";ET;}
using namespace std;
typedef long long ll;

int ls=-1;

int guess(int x)
{
	//printf("guess %d: ",x);
	int t=Guess(x);
	//printf("%d\n",t);
	ls=x;
	return t;
}

void handle(int &l,int &r)
{
	while(l<r)
	{
		int m=l+r>>1;
		if(ls!=l&&ls!=r)
			guess(l);
		if(ls==l)
		{
			if(l==m)
			{
				if(guess(r)==-1) r=l;
				else l=r;
				break;
			}
			int t=guess(m);
			if(t==0)
			{
				l=r=(l+m)/2;
				break;
			}
			else if(t==-1) r=(l+m)/2-((l+m)%2==0);
			else
			{
				t=guess(r);
				if(t==0)
				{
					l=r=(m+r)/2;
					break;
				}
				else if(t==-1)
				{
					l=(l+m)/2+1,r=(m+r)/2-((m+r)%2==0);
					break;
				}
				else l=(m+r)/2+1;
			}
		}
		else
		{
			int t=guess(m);
			if(l==m)
			{
				if(t==-1) l=r;
				else r=l;
				break;
			}
			if(t==0)
			{
				l=r=(m+r)/2;
				break;
			}
			else if(t==-1) l=(m+r)/2+1;
			else
			{
				t=guess(l);
				if(t==0)
				{
					l=r=(l+m)/2;
					break;
				}
				else if(t==-1)
				{
					l=(l+m)/2+1,r=(m+r)/2-((m+r)%2==0);
					break;
				}
				else
					r=(l+m)/2-((l+m)%2==0);
			}
		}
	}
}

int HC(int N)
{
	ls=-1;
	int l=1,r=N;
	handle(l,r);
	while(l<r)
	{
		if(l+r-ls<1||l+r-ls>N)
			guess(l);
		int m=l+r>>1,tmp=ls,t=guess(l+r-ls);
		if(t==0)
		{
			l=r=m;
			break;
		}
		else if(t==-1)
			if(tmp>ls) l=m+1;
			else r=m-((l+r)%2==0);
		else
			if(tmp>ls) r=m-((l+r)%2==0);
			else l=m+1;
	}
	return l;
}

Compilation message

hottercolder.cpp: In function 'void handle(int&, int&)':
hottercolder.cpp:32:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m=l+r>>1;
         ~^~
hottercolder.cpp: In function 'int HC(int)':
hottercolder.cpp:110:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m=l+r>>1,tmp=ls,t=guess(l+r-ls);
         ~^~

Subtask #1
25.0 / 25.0

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

Subtask #2
25.0 / 25.0

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

Subtask #3
25.0 / 25.0

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

Subtask #4
12.0 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 693 ms 8236 KB Output is partially correct - alpha = 0.500000000000