Submission #73231

#	Time	Username	Problem	Language	Result	Execution time	Memory
73231		Sa1378	The Big Prize (IOI17_prize)	C++17	96.73 / 100	182 ms	4792 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
#define N ((int)201*1000)

int n,arr[N],lft[N],rght[N];
int cnt_rght[N],cnt_lft[N];
bool mark[N];

bool query(int x)
{
	if(lft[x]+rght[x]>0)return 0;
	vector <int> vec;vec=ask(x);
	lft[x]=vec[0];rght[x]=vec[1];
	return (lft[x]+rght[x]==0);
}

void add(int x)
{
	mark[x]=1;
	for(int i=x+1;i<n;i++)cnt_lft[i]++;
	for(int i=x-1;i>=0;i--)cnt_rght[i]++;
	return ;
}


int find_best(int n2)
{
	n=n2;
	for(int i=0;i<n;i++)arr[i]=i;
	srand(time(NULL));
	random_shuffle(arr,arr+n);
	int now=0,id;
	for(int i=0;i<600;i++)
	{
		if(query(arr[i]))return arr[i];
		if(now<lft[arr[i]]+rght[arr[i]])
			now=lft[arr[i]]+rght[arr[i]],id=arr[i];
	}
	for(int i=0;i<600;i++)
		if(now>lft[arr[i]]+rght[arr[i]])
			add(arr[i]);
	while(1)
	{
		int l=-1,r=n;
		while(l<r-1)
		{
			int mid=(l+r)/2;
			for(int i=0;;i++)
			{
				if(mid+i<r && !mark[mid+i])
				{
					mid=mid+i;
					break;
				}
				if(mid-i>l && !mark[mid-i])
				{
					mid=mid-i;
					break;
				}
			}
			if(query(mid))return mid;
			if(lft[mid]+rght[mid]<now)
			{
				add(mid);
				break;
			}
			if((rght[mid]-cnt_rght[mid])-(rght[r]-cnt_rght[r])>0)l=mid;
			else r=mid;
		}
	}
	
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:33:12: warning: variable 'id' set but not used [-Wunused-but-set-variable]
  int now=0,id;
            ^~

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