Submission #137541

#	Time	Username	Problem	Language	Result	Execution time	Memory
137541		Mahdi_Jfri	The Big Prize (IOI17_prize)	C++14	20 / 100	119 ms	5348 KiB

prize

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

using namespace std;

#define ll long long
#define pb push_back

const int maxn = 2e5 + 20;

vector<int> res[maxn] , candid;

int mx;

vector<int> reval(int k)
{
	if(!res[k].empty())
		return res[k];

	res[k] = ask(k);
	while(res[k][0] + res[k][1] > mx);
	return res[k];
}

void solve(int l , int r)
{
	while(l < r)
	{
		auto tmp = reval(l);
		if(tmp[0] + tmp[1] != mx)
			candid.pb(l++);
		else
			break;
	}
	while(l < r)
	{
		r--;
		auto tmp = reval(r);
		if(tmp[0] + tmp[1] != mx)
			candid.pb(r);
		else
			break;
	}

	if(l >= r)
		return;

	reval(l); reval(r);
	if(res[r][0] - res[l][0] == 0)
		return;

	int m = (l + r) / 2;
	solve(m , r + 1);
	solve(l , m);
}

int find_best(int n)
{
	if(n <= 5000)
	{
		for(int i = 0; i < n; i++) {
			std::vector<int> res = ask(i);
			if(res[0] + res[1] == 0)
				return i;
		}
	}

	for(int i = 0; i < 1000; i++)
	{
		vector<int> tmp = ask(i);
		mx = max(mx , tmp[0] + tmp[1]);
	}

	solve(0 , n);

	for(auto x : candid)
	{
		auto tmp = reval(x);
		if(tmp[0] + tmp[1] == 0)
			return x;
	}
	return -85;
}

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