Submission #289457

#	Time	Username	Problem	Language	Result	Execution time	Memory
289457		eohomegrownapps	The Big Prize (IOI17_prize)	C++14	90 / 100	130 ms	2024 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 find_best(int N) {
	n=N;
	lcache.resize(n,-1);
	rcache.resize(n,-1);
	if (n<=600){
		for (int i = 0; i < n; i++) {
			if(asksum(i) == 0){
				return i;
			}
		}
		assert(1==0);
	}
	int maxsum = 0;
	int maxind = -1;
	for (int i = 0; i<600; i++){
		int res = asksum(i);
		if (res==0){return i;}
		if (res>maxsum){
			maxsum=res;
			maxind=i;
		}
	}
	// first ind is at maxind
	int ptr = maxind;
	while (ptr<n){
		//cout<<ptr<<endl;
		auto res = askmap(ptr);
		if (res.first+res.second==0){return ptr;}
		if (res.first+res.second<maxsum){
			ptr++;
			continue;
		}
		// otherwise find stretch equal to this value
		int l = 0, r = 1;
		while (ptr+r<n){
			auto rs = askmap(ptr+r);
			if (rs.first+rs.second==0){return ptr;}
			if (rs!=res){
				break;
			}
			l=r-1;
			r<<=1;
		}
		r=min(r,n-1-ptr);
		//cout<<"check "<<ptr+l<<' '<<ptr+r<<endl;
		while (l<=r){
			int m = (l+r)/2;
			if (asksum(ptr+m)==0){return ptr+m;}
			if (askmap(ptr+m)!=res){
				r=m-1;
			} else {
				l=m+1;
			}
		}
		ptr+=l;
	}
	assert(1==0);
	return 0;
}

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