Submission #268697

#	Time	Username	Problem	Language	Result	Execution time	Memory
268697		Plurm	The Big Prize (IOI17_prize)	C++11	100 / 100	55 ms	5368 KiB

prize

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

vector<int> memoiz[200005];
int key = -1;
vector<int> customAsk(int x){
	// Memoized version of ask
	if(memoiz[x].empty()) memoiz[x] = ask(x);
	key = max(key, memoiz[x][0] + memoiz[x][1]);
	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] != key){
		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] != key){
			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;
}
void popularPreprocess(int l, int r, int& left, int dep = 0){
	if(l >= r) return;
	if(left <= 0) return;
	int m = (l+r)/2;
	customAsk(m);
	left--;
	popularPreprocess(l, m-1, left);
	if(dep > 3)
	popularPreprocess(m+1, r, left);
}
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 cntr = sqrt(n);
	popularPreprocess(0, n-1, cntr);
	int ans = solve(0, n-1);
	for(int i = 0; i < n; i++) memoiz[i].clear();
	return ans;
}

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