Submission #286859

#	Time	Username	Problem	Language	Result	Execution time	Memory
286859		egekabas	The Big Prize (IOI17_prize)	C++14	97.95 / 100	62 ms	5248 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<int, int> pii;
typedef pair<ld, ld> pld;
	
int ans = -1;
int curval;
vector<int> dp[200009];
vector<int> q(int x){
	if(dp[x].size())
		return dp[x];
	return dp[x] = ask(x);
}
void binsearch(int l, int r, int lval, int rval){
	int cnt = curval-lval-rval;
	if(cnt == 0 || l > r || ans != -1)
		return;
	int mid = (l+r)/2;
	for(int i = 0; (mid-i) >= l || (mid+i) <= r; ++i){
		int extra = 0;
		if(ans != -1 || cnt <= 0) return;
		if((mid-i) >= l){
			int id = (mid-i);
			vector<int> res = q(id);
			if(ans != -1) return;
			if(res[0]+res[1] == curval){
				binsearch(l, id-1, lval, res[1]);
				binsearch(max(mid+i,mid+1), r, res[0]+extra, rval);
				return;
			}
			else if(res[0]+res[1] == 0){
				ans = id;
				return;
			}
			else{
				--cnt;
				++extra;
			}
		}
		if(ans != -1 || cnt <= 0) return;
		if(i != 0 && (mid+i) <= r){
			int id = mid+i;
			vector<int> res = q(id);
			if(ans != -1) return;
			if(res[0]+res[1] == curval){
				binsearch(l, mid-i-1, lval, res[1]+extra);
				binsearch(id+1, r, res[0], rval);
				return;
			}
			else if(res[0]+res[1] == 0){
				ans = id;
				return;
			}
			else{
				--cnt;
				++extra;
			}
		}
	}
}
int find_best(int n) {
	srand(time(NULL));
	int times = 470;
	while(times--){
		vector<int> res = q(rand()%n);
		curval = max(curval, res[0]+res[1]);
	}
	binsearch(0, n-1, 0, 0);
	assert(ans != -1 && q(ans)[0] == 0 && q(ans)[1] == 0);
	return ans;
}

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