Submission #73237

#	Time	Username	Problem	Language	Result	Execution time	Memory
73237		Sa1378	The Big Prize (IOI17_prize)	C++17	20 / 100	1075 ms	4024 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;
	int now=0,id;
	queue <pair<int,int> > q;
	q.push({-1,n});
	for(int i=0;i<300;i++)
	{
		int l=q.front().first,r=q.front().second;q.pop();
		int mid=(l+r)/2;
		if(query(mid))return mid;
		if(now<lft[mid]+rght[mid])
			now=lft[mid]+rght[mid],id=mid;
		q.push({mid,r});
		q.push({l,mid});
	}
	while(q.size())q.pop();
	q.push({-1,n});
	for(int i=0;i<300;i++)
	{
		int l=q.front().first,r=q.front().second;q.pop();
		int mid=(l+r)/2;
		if(now>lft[mid]+rght[mid])
			add(mid);
		q.push({mid,r});
		q.push({l,mid});
	}
	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:30:12: warning: variable 'id' set but not used [-Wunused-but-set-variable]
  int now=0,id;
            ^~

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