Submission #96380

#	Time	Username	Problem	Language	Result	Execution time	Memory
96380		figter001	The Big Prize (IOI17_prize)	C++14	100 / 100	67 ms	10284 KiB

prize

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

using namespace std;

typedef long long ll;
const int maxn = 2e5+50;

int ans,n;
map<int,vector<int>> mp[maxn];

void solve(int l,int r){
	if(l > r || ans != -1)return;
	int md = (l+r)/2;
	vector<int> res = ask(md);
	if(res[0] + res[1] == 0){
		ans = md;
		return;
	}
	int sum = res[0] + res[1];
	auto it = mp[sum].upper_bound(md);
	bool x=1,y=1;
	if(it != mp[sum].end()){
		if(it->second[0] == res[0])
			x = 0;
	}
	if(it != mp[sum].begin())
		it--;
	if(it != mp[sum].begin()){
		if(it->second[1] == res[1])
			y = 0;
	}
	mp[sum][md] = res;
	if(y)solve(l,md-1);
	if(x)solve(md+1,r);
}

int find_best(int N) {
	n = N;
	ans = -1;
	solve(0,n-1);
	return ans;
}

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