Submission #601151

#	Time	Username	Problem	Language	Result	Execution time	Memory
601151		Lucpp	The Big Prize (IOI17_prize)	C++17	20 / 100	3051 ms	348 KiB

prize

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

int MAX = 500;
int v;

map<int, vector<int>> memo;
vector<int> qry(int i){
	if(memo.count(i)) return memo[i];
	vector<int> a = ask(i);
	return memo[i] = a;
}

int ans = -1;

void solve(int l, int r, int subL, int subR){
	if(r < l) return;
	int m = (l+r)/2;
	int lo = m-1, hi = m;
	int it = 0;
	int cnt = 0;
	while(true){
		if(ans != -1) return;
		if(it == 0) m = hi++;
		else m = lo--;
		if(lo < l && hi > r) break;
		if(m < l || m > r) continue;;
		vector<int> a = qry(m);
		if(a[0]+a[1] == 0){
			ans = m;
			return;
		}
		if(a[0]+a[1] != v){
			cnt++;
			continue;
		}
		if(it == 0){
			if(cnt < a[0]-subL) solve(l, lo, subL, cnt+a[1]);
			if(0 < a[1]-subR) solve(hi, r, a[0]+cnt, subR);
		}
		else{
			if(0 < a[0]-subL) solve(l, lo, subL, cnt+a[1]);
			if(cnt < a[1]-subR)solve(hi, r, a[0]+cnt, subR);
		}
	}
}

int find_best(int n) {
	MAX = min(n, MAX);
	v = 0;
	for(int i = 0; i < MAX; i++){
		vector<int> a = qry(i);
		if(a[0] + a[1] == 0) return i;
		v = max(v, a[0]+a[1]);
	}
	solve(0, n-1, 0, 0);
	return ans;
}

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