Submission #339655

#	Time	Username	Problem	Language	Result	Execution time	Memory
339655		ogibogi2004	The Big Prize (IOI17_prize)	C++14	90 / 100	93 ms	2284 KiB

prize

#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+6;
pair<int,int> answer[MAXN];
vector<int>valuable;
int maxs=0;
pair<int,int>q;
vector<int>lollipops;
char lorv[MAXN];
pair<int,int> get_answer(int i)
{
	//cout<<i<<endl;
	if(answer[i].first!=-1)return answer[i];
	vector<int>q=ask(i);
	answer[i].first=q[0];
	answer[i].second=q[1];
	return answer[i];
}
void bs(int l,int r)
{
	if(l>r)return;
	pair<int,int> ivan=get_answer(l);
	if(l==r)
	{
		if(ivan.first+ivan.second!=maxs)
		{
			valuable.push_back(l);
		}
		return;
	}
	if(ivan.first+ivan.second!=maxs)
	{
		valuable.push_back(l);
		bs(l+1,r);
		return;
	}
	ivan=get_answer(r);
	if(ivan.first+ivan.second!=maxs)
	{
		valuable.push_back(r);
		bs(l,r-1);
		return;
	}
	if(get_answer(r).first==get_answer(l).first)return;
	int mid,low=l,high=r,ans=-1;
	while(low<=high)
	{
		mid=(low+high)/2;
		ivan=get_answer(mid);
		if(ivan.first+ivan.second!=maxs)
		{
			ans=mid;
			break;
		}
		if(ivan.first>get_answer(l).first)
		{
			high=mid-1;
		}
		else low=mid+1;
	}
	if(ans==-1)return;
	valuable.push_back(ans);
	bs(l+1,ans-1);
	bs(ans+1,r);
}
int find_best(int n) {
	if(n<=5000)
	{
		for(int i=0;i<n;i++)
		{
			vector<int>t=ask(i);
			if(t[0]+t[1]==0)
			{
				return i;
			}
		}
	}
	//cout<<"*\n";
	for(int i=0;i<n;i++)answer[i]={-1,-1};
	
	for(int i=0;i<500;i++)
	{
		q=get_answer(i);
		if(q.first+q.second==0)
		{
			/*for(int j=0;j<=200000000;j++)
			{
				j=4*j-3*j;
				answer[j%500]=answer[j%500];
				lorv[j%500]='Z';
			}*/
			return i;
		}
		answer[i]=q;
		maxs=max(maxs,q.first+q.second);
	}
	
	bs(0,n-1);
	
	
	/*for(int i=0;i<n;i++)lorv[i]='?';
	for(int i=0;i<500;i++)
	{
		if(answer[i].first+answer[i].second==maxs)
		{
			lorv[i]='L';
			lollipops.push_back(i);
		}
		else
		{
			lorv[i]='V';
			valuable.push_back(i);
		}
	}
	bs(500,n-1);*/
	//assert(false);
	for(auto j:valuable)
	{
		if(get_answer(j).first+get_answer(j).second==0)
		{
			return j;
		}
	}
	//assert(false);
	return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 70 / 80