Submission #423286

#	Time	Username	Problem	Language	Result	Execution time	Memory
423286		albertolg101	The Big Prize (IOI17_prize)	C++17	90 / 100	105 ms	5392 KiB

prize

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

using namespace std; 

int find_best(int n) {

	int sum = 0, pos = -1;
	vector<int> ar;
	
	int k = 500;

	for(int i = 0 ; i < k ; i++)
	{
		ar = ask(i);

		if(ar[0] + ar[1] == 0)
			return i;

		sum = max(sum, ar[0] + ar[1]);
	}

	pos = k - 1;

	while(true)
	{
		pos++;
		ar = ask(pos);
		if(ar[0] + ar[1] == 0)
			return pos;

		if(ar[0] + ar[1] == sum)
			break;
	}

	vector<vector<int>> query(n);

	function<vector<int>(int)> f = [&](int x)
	{
		if(query[x].empty())
			query[x] = ask(x);

		return query[x];
	};

	function<bool(int, int)> rng = [&](int l, int r)
	{
		f(l), f(r);

		if(query[l][0] + query[l][1] == query[r][0] + query[r][1] and query[l][0] + query[l][1] == sum and 0 == query[r][0] - query[l][0])
			return false;
		
		return true;
	};

	function<int(int, int)> dandc = [&](int l, int r)
	{
		if(l == r)
			return (query[l][0] + query[r][1] == 0 ? l : -1);

		int mid = (l + r) / 2, ans = -1;

		if(rng(l, mid))
			ans = max(ans, dandc(l, mid));

		if(rng(mid+1, r))
			ans = max(ans, dandc(mid+1, r));

		return ans;
	};

	return dandc(pos, n-1);
}

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