Submission #268682

#	Time	Username	Problem	Language	Result	Execution time	Memory
268682		Plurm	The Big Prize (IOI17_prize)	C++11	20 / 100	45 ms	5380 KiB

prize

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

vector<int> memoiz[200005];
vector<int> customAsk(int x){
	// Memoized version of ask
	if(memoiz[x].empty()) return memoiz[x] = ask(x);
	else return memoiz[x];
}

int solve(int l, int r, int offsL = 0, int offsR = 0){
	if(l > r) return -1;
	if(l == r) return customAsk(l)[0] + customAsk(l)[1] == 0 ? l : -1;
	int m = (l+r)/2;
	vector<int> res = customAsk(m);
	while(res[0] + res[1] < 1){
		if(res[0] + res[1] == 0) return m;
		if(m == r) break;
		m++;
		res = customAsk(m);
	}
	if(m == r){
		m = (l+r)/2;
		while(res[0] + res[1] < 1){
			if(res[0] + res[1] == 0) return m;
			if(m == l) return -1;
			m--;
			res = customAsk(m);
		}
	}
	int left = -1;
	if(res[0] - offsL > 0) left = solve(l, m-1, offsL, res[1]);
	if(left != -1) return left;
	if(res[1] - offsR > 0) return solve(m+1, r, res[0], offsR);
	return -1;
}

int find_best(int n) {
	if(n < 5000){
		for(int i = 0; i < n; i++) {
			vector<int> res = customAsk(i);
			if(res[0] + res[1] == 0)
				return i;
		}
	}
	int ans = solve(0, n-1);
	for(int i = 0; i < n; i++) memoiz[i].clear();
	return ans;
}

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