Submission #73227

#	Time	Username	Problem	Language	Result	Execution time	Memory
73227		Sa1378	The Big Prize (IOI17_prize)	C++17	90 / 100	337 ms	5692 KiB

prize

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

int n,arr[N],a[N],sz,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(69);
	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)
	{
		sz=0;
		for(int i=0;i<n;i++)
			if(!mark[i])
				a[sz++]=i;
		a[sz]=n;
		int l=-1,r=sz;
		while(l<r-1)
		{
			int mid=(l+r)/2;
			if(query(a[mid]))return a[mid];
			if(lft[a[mid]]+rght[a[mid]]<now)
			{
				add(a[mid]);
				break;
			}
			if((rght[a[mid]]-cnt_rght[a[mid]])-(rght[a[r]]-cnt_rght[a[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: 70 / 80