Submission #831036

#	Time	Username	Problem	Language	Result	Execution time	Memory
831036		LIF	The Big Prize (IOI17_prize)	C++14	97.90 / 100	45 ms	2000 KiB

prize

#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
int ll[300005];
int rr[300005];
int maxn = -1;
vector<int> ans;
int last = -1;
void find(int l,int r,int nowsize)
{
	if(l == r)
	{
		ans.push_back(l);
		return;
	}
	bool flag = true;
	while(l <= r)
	{
		if(ll[l] == -1)
		{
			vector<int> temp = ask(l);
			ll[l] = temp[0];rr[l] = temp[1];
			if(ll[l] + rr[l] == maxn)break;
			else 
			{
				//if(ll[l] + rr[l] == 0)last = l;
				ans.push_back(l);
				l++;
			}
		}
		else
		{
			if(ll[l] + rr[l] == maxn)break;
			else 
			{
				ans.push_back(l);
				l++;
			}
		}
	}
	while(l <= r)
	{
		if(rr[r] == -1)
		{
			vector<int> temp = ask(r);
			ll[r] = temp[0];rr[r] = temp[1];
			if(ll[r] + rr[r] == maxn)break;
			else
			{
				ans.push_back(r);
				r--;
			}
		}
		else
		{
			if(ll[r] + rr[r] == maxn)break;
			else
			{
				ans.push_back(r);
				r--;
			}
		}
	}
	if(l > r)return;
	int mid1 = (l+r)>>1;
	int mid2 = (l+r)>>1;
	while(mid1 >= l)
	{
		if(rr[mid1] == -1)
		{
			vector<int> temp = ask(mid1);
			ll[mid1] = temp[0];rr[mid1] = temp[1];
			if(ll[mid1] + rr[mid1] == maxn)break;
			else
			{
				ans.push_back(mid1);
				mid1--;
			}
		}
		else
		{
			if(ll[mid1] + rr[mid1] == maxn)break;
			else
			{
				ans.push_back(mid1);
				mid1--;
			}
		}
	}
	int xx = ll[mid1] - ll[l];
	if(xx != 0)find(l,mid1,xx);

	while(mid2 <= r)
	{
		if(ll[mid2] == -1)
		{
			vector<int> temp = ask(mid2);
			ll[mid2] = temp[0];rr[mid2] = temp[1];
			if(ll[mid2] + rr[mid2] == maxn)break;
			else 
			{
				ans.push_back(mid2);
				mid2++;
			}
		}
		else
		{
			if(ll[mid2] + rr[mid2] == maxn)break;
			else 
			{
				ans.push_back(mid2);
				mid2++;
			}
		}
	}
	xx = ll[r] - ll[mid2];
	if(xx!=0)find(mid2,r,xx);

	return;
}
int find_best(int n)
{
	srand(time(0));
	for(int i=0;i<n;i++)ll[i] = -1;
	for(int i=0;i<n;i++)rr[i] = -1;
	int first = 0;
	int xx = 475;
	for(int pp=0;pp<xx;pp++)
	{
		int i = rand() % n;
		vector<int> a = ask(i);
		int su = a[0] + a[1];
		ll[i] = a[0];rr[i] = a[1];
		if(su == 0)return i;
		if(su > maxn)
		{
			maxn = su;
			first = i;
		}
	}
	find(0,first-1,ll[first]);
	find(first+1,n-1,rr[first]);
	for(int i=0;i<ans.size();i++)
	{
		if(ll[ans[i]] +rr[ans[i]] == 0)return ans[i];
	}
	return 0;
}

Compilation message (stderr)

prize.cpp: In function 'void find(int, int, int)':
prize.cpp:16:7: warning: unused variable 'flag' [-Wunused-variable]
   16 |  bool flag = true;
      |       ^~~~
prize.cpp: In function 'int find_best(int)':
prize.cpp:143:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  143 |  for(int i=0;i<ans.size();i++)
      |              ~^~~~~~~~~~~

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