Submission #593764

#	Time	Username	Problem	Language	Result	Execution time	Memory
593764		yutabi	The Big Prize (IOI17_prize)	C++14	90 / 100	59 ms	336 KiB

prize

#include "prize.h"


#include <bits/stdc++.h>
using namespace std;


#define pb push_back


vector <bool> arr1_bad(200007,0);

vector <bool> arr2_bad(600,0);



int N;

int heavy1;
int heavy2;

int query1(int loc)
{
	//printf("1 %d",loc);

	loc++;

	int l=0;
	int r=N-1;

	int m=(l+r)/2;

	int left=0;

	while(l!=r)
	{
		while(arr1_bad[m]==1 && m>l)
		{
			m--;
		}

		if(m==l && arr1_bad[m]==1)
		{
			m=(l+r)/2;

			if(left+m-l+1>=loc)
			{
				//printf(" %d\n",l+loc-left-1);

				return l+loc-left-1;
			}

			left+=m-l+1;
			l=m+1;

			m=(l+r)/2;

			continue;
		}

		vector <int> res=ask(m);

		if(res[0]+res[1]<heavy1)
		{
			arr1_bad[m]=1;

			continue;
		}

		if(res[0]<loc)
		{
			l=m+1;

			left=res[0];
		}

		else
		{
			r=m;
		}


		m=(l+r)/2;
	}

	//printf(" %d\n",l);

	return l;
}

int query2(int loc)
{
	//printf("2 %d",loc);

	loc++;

	int l=0;
	int r=heavy1-1;

	int m=(l+r)/2;

	int left=0;

	while(l!=r)
	{
		while(arr2_bad[m]==1 && m>l)
		{
			m--;
		}

		if(m==l && arr2_bad[m]==1)
		{
			m=(l+r)/2;

			if(left+m-l+1>=loc)
			{
				//printf(" %d\n",l+loc-left-1);

				return l+loc-left-1;
			}

			left+=m-l+1;
			l=m+1;

			m=(l+r)/2;

			continue;
		}

		vector <int> res=ask(query1(m));

		if(res[0]+res[1]<heavy2)
		{
			arr2_bad[m]=1;

			continue;
		}

		if(res[0]<loc)
		{
			l=m+1;

			left=res[0];
		}

		else
		{
			r=m;
		}


		m=(l+r)/2;
	}

	//printf(" %d\n",l);

	return l;
}



int find_best(int n)
{
	N=n;
	for(int i=0;i<min(600,n);i++)
	{
		vector <int> res=ask(i);

		heavy1=max(heavy1,res[0]+res[1]);
	}

	if(heavy1==1)
	{
		int l=0;
		int r=n-1;
		int m=(l+r)/2;

		while(l!=r)
		{
			vector <int> res=ask(m);

			if(res[1]==0)
			{
				r=m;
			}

			else
			{
				l=m+1;
			}

			m=(l+r)/2;
		}

		return m;
	}

	for(int i=0;i<min(30,heavy1);i++)
	{
		vector <int> res=ask(query1(i));

		heavy2=max(heavy2,res[0]+res[1]);
	}

	for(int i=0;1;i++)
	{
		vector <int> res=ask(query1(query2(i)));

		if(res[0]+res[1]==0)
		{
			return query1(query2(i));
		}
	}


	return 0;
}

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