Submission #59165

#	Time	Username	Problem	Language	Result	Execution time	Memory
59165		TadijaSebez	The Big Prize (IOI17_prize)	C++11	100 / 100	69 ms	10268 KiB

prize

#include <stdio.h>
#include <map>
#include <vector>
using namespace std;
#define mp make_pair
vector<int> ask(int i);
const int N=200050;
map<int,pair<int,int> > all[N];
map<int,pair<int,int> >::iterator it;
pair<int,int> Get(int i)
{
	vector<int> x=ask(i);
	return mp(x[0],x[1]);
}
int sol=-1;
void Solve(int l, int r)
{
	if(~sol || l>r) return;
	int mid=l+r>>1;
	pair<int,int> tmp=Get(mid);
	int sz=tmp.first+tmp.second;
	if(sz==0){ sol=mid;return;}
	it=all[sz].upper_bound(mid);
	bool lf=1,rf=1;
	if(it!=all[sz].end() && it->second.first==tmp.first) rf=0;
	if(it!=all[sz].begin())
	{
		it--;
		if(it->second.first==tmp.first) lf=0;
	}
	all[sz][mid]=tmp;
	if(lf) Solve(l,mid-1);
	if(rf) Solve(mid+1,r);
}
int find_best(int n)
{
	Solve(0,n-1);
	return sol;
}

Compilation message (stderr)

prize.cpp: In function 'void Solve(int, int)':
prize.cpp:19:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=l+r>>1;
          ~^~

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