Submission #423291

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

prize

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

using namespace std; 

int find_best(int n) {

	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 0 == query[r][0] - query[l][0])
			return false;
		
		return true;
	};

	function<int(int, int)> dandc = [&](int l, int r)
	{
		int mid = (l + r) / 2;
		f(mid);

		if(query[mid][0] + query[mid][1] == 0)
			return mid;

		int 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;
	};

	if(f(0)[0] + f(0)[1] == 0)
		return 0;

	if(f(n-1)[0] + f(n-1)[1] == 0)
		return n-1;

	return dandc(0, n-1);
}

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