Submission #138921

#	Time	Username	Problem	Language	Result	Execution time	Memory
138921		Lawliet	The Big Prize (IOI17_prize)	C++14	0 / 100	7 ms	588 KiB

prize

#include <bits/stdc++.h>
#include "prize.h"

#define MAX 200010

using namespace std;
typedef pair<int,int> pii;

bool marc[MAX];

pii ans[MAX];

vector<int> expensivePrizes;

queue<pii> q;

void query(int i)
{
	if( marc[i] ) return;

	marc[i] = true;

	vector<int> k = ask( i );

	ans[ i ] = {k[ 0 ] , k[ 1 ]};
}

int getMoreExpensive(int l, int r)
{
	query( l ); query( r );

	return ans[r].first - ans[l].first;
}

int find_best(int n)
{
	if(n <= 5000)
	{
		for(int g = 0 ; g < 5000 ; g++)
		{
			query( g );

			if(ans[g].first + ans[g].second == 0) return g;
		}
	}

	int lollipopVal = 0;

	for(int g = 0 ; g < 474 ; g++)
	{
		query( g );

		lollipopVal = max(lollipopVal , ans[g].first + ans[g].second);
	}

	int l = 0, r = n - 1;

	for(int g = 0 ; g < 474 ; g++)
	{
		if(ans[g].first + ans[g].second == lollipopVal) l = g;
		else expensivePrizes.push_back( g );
	}

	while( true )
	{
		query( r );

		if(ans[r].first + ans[r].second == lollipopVal) break;

		expensivePrizes.push_back( r-- );
	}

	q.push({l , r});

	while( true )
	{
		pii curInterval = q.front();
		q.pop();

		int curL = curInterval.first;
		int curR = curInterval.second;
		int mid = (curL + curR)/2;

		int newL = mid;
		int newR = mid;

		while( newL <= curR )
		{
			query( newL );

			if(ans[newL].first + ans[newL].second == lollipopVal) break;

			expensivePrizes.push_back( newL++ );
		}

		while( curL <= newR )
		{
			query( newR );

			if(ans[newR].first + ans[newR].second == lollipopVal) break;

			expensivePrizes.push_back( newR-- );
		}

		if(getMoreExpensive(curL , newR) > 0) q.push({curL , newR});
		if(getMoreExpensive(newL , curR) > 0) q.push({newL , curR});
	}

	for(int g = 0 ; g < expensivePrizes.size() ; g++)
	{
		int cur = expensivePrizes[g];

		if(ans[cur].first + ans[cur].second == 0) return cur;
	}
}

/*int main()
{
	int nn;
	scanf("%d",&nn);

	printf("%d\n",find_best(nn));
}*/

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:109:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int g = 0 ; g < expensivePrizes.size() ; g++)
                  ~~^~~~~~~~~~~~~~~~~~~~~~~~

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