Submission #294421

#	Time	Username	Problem	Language	Result	Execution time	Memory
294421		eohomegrownapps	The Big Prize (IOI17_prize)	C++14	96.33 / 100	101 ms	2052 KiB

prize

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

vector<int> lcache;
vector<int> rcache;
int n;

pair<int,int> askmap(int i){
	//cout<<"askmap "<<i<<endl;
	if (i>=n){
		return {1e9,1e9};
	}
	assert(i<n);
	if (lcache[i]==-1){
		vector<int> res = ask(i);
		lcache[i] = res[0];
		rcache[i] = res[1];
	}
	return {lcache[i],rcache[i]};
}

int asksum(int i){
	auto p = askmap(i);
	return p.first+p.second;
}

int lsum = 0;

int dnc(int s, int e, int numexp, int prefexp, int suffexp){
	// numexp expensive things in range s->e
	//cout<<s<<' '<<e<<' '<<numexp<<' '<<prefexp<<' '<<suffexp<<endl;
	if (e-s+1==numexp){
		for (int i = s; i<=e; i++){
			if (asksum(i)==0){return i;}
		}
		return -1;
	}
	if (numexp==0){
		return -1;
	}
	// there is at least one lollipop
	int m = (s+e)/2;
	for (int i = m; i>=s; i--){
		if (asksum(i)==lsum){
			auto m = askmap(i);
			int lval = m.first;
			int rval = m.second;
			
			int dl = dnc(s,i-1,lval-prefexp, prefexp, rval);
			if (dl!=-1){return dl;}
			int dr = dnc(i+1,e,rval-suffexp, lval, suffexp);
			if (dr!=-1){return dr;}
			return -1;
		} else if (asksum(i)==0){
			return i;
		}
	}
	for (int i = m+1; i<=e; i++){
		if (asksum(i)==lsum){
			auto m = askmap(i);
			int lval = m.first;
			int rval = m.second;
			
			//int dl = dnc(s,i-1,lval-prefexp, prefexp, rval);
			//if (dl!=-1){return dl;}
			int dr = dnc(i+1,e,rval-suffexp, lval, suffexp);
			if (dr!=-1){return dr;}
			return -1;
		} else if (asksum(i)==0){
			return i;
		}
	}
	assert(1==0);
}

int find_best(int N) {
	n=N;
	lcache.resize(n,-1);
	rcache.resize(n,-1);
	if (n<=500){
		for (int i = 0; i < n; i++) {
			if(asksum(i) == 0){
				return i;
			}
		}
		assert(1==0);
	}
	int m = (n-1)/2;
	for (int i = m-240; i<m+240; i++){
		int res = asksum(i);
		if (res==0){return i;}
		lsum = max(res,lsum);
	}
	
	return dnc(0,n-1,lsum,0,0);
}

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