Submission #441824

#	Time	Username	Problem	Language	Result	Execution time	Memory
441824		prvocislo	The Big Prize (IOI17_prize)	C++17	100 / 100	65 ms	10688 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;

const int maxn = 2e5 + 5;
int ans[maxn];
set<int> typ[maxn];
int rek(int l, int r)
{
	if (r < l) return -1;
	int m = (l + r) >> 1;
	vector<int> v = ask(m);
	int sum = v[0] + v[1]; ans[m] = v[0];
	if (!sum) return m;
	auto it = typ[sum].insert(m).first;
	if (it == typ[sum].begin() || ans[*prev(it)] != ans[*it])
	{
		int val = rek(l, m-1);
		if (val != -1) return val;
	}
	if (next(it) == typ[sum].end() || ans[*next(it)] != ans[*it])
	{
		int val = rek(m+1, r);
		if (val != -1) return val;
	}
	return -1;
}
int find_best(int n) 
{
	return rek(0, n-1);
}

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