Submission #268129

#	Time	Username	Problem	Language	Result	Execution time	Memory
268129		Plurm	The Big Prize (IOI17_prize)	C++11	0 / 100	89 ms	5368 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, int offsR){
	if(l == r) return -1;
	int m = (l+r)/2;
	vector<int> res = customAsk(m);
	if(res[0] + res[1] == 0) return 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 b = sqrt(n);
	vector<tuple<int,int,int,int> > eachBlock; // (L, R, offsL, offsR)
	int last = 0;
	int lidx = -1;
	for(int i = b; i < n;){
		vector<int> cur = customAsk(i);
		if(cur[0] + cur[1] <= 2*b){
			i++;
		}else{
			eachBlock.emplace_back(lidx+1, i, last, cur[1]);
			last = cur[0];
			lidx = i;
			i += b;
		}
	}
	if(lidx != n-1) eachBlock.emplace_back(lidx+1, n-1, last, 0);
	for(auto block : eachBlock){
		int l,r,ofl,ofr;
		tie(l,r,ofl,ofr) = block;
		int ret = solve(l, r, ofl, ofr);
		if(ret != -1) return ret;
	}
	return 0;
}

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