Submission #70318

#	Time	Username	Problem	Language	Result	Execution time	Memory
70318		gnoor	The Big Prize (IOI17_prize)	C++17	100 / 100	69 ms	2116 KiB

prize

#include "prize.h"

#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

int lft[200100];
int rgt[200100];

int _ask(int x) {
	if (lft[x]!=-1) return lft[x]+rgt[x];
	auto res = ask(x);
	lft[x]=res[0];
	rgt[x]=res[1];
	return lft[x]+rgt[x];
}

int mx=-1;

int ans=-1;

bool solve(int l,int r,int sl,int sr) {
	int m=(l+r)>>1;
	int res;
	while (m<=r) {
		res=_ask(m);
		if (res==0) {
			ans=m;
			return false;
		}
		if (res>mx) {
			mx=res;
			return false;
		}
		if (res==mx) break;
		m++;
	}
	if (m>r) {
		//not found
		m=(l+r)>>1;
		m--;
		while (m>=l) {
			res=_ask(m);
			if (res==0) {
				ans=m;
				return false;
			}
			if (res>mx) {
				mx=res;
				return false;
			}
			if (res==mx) break;
			m--;
		}
		if (m<l) {
			//not found
			return true;
		}
	}
	//normal
	int ll=lft[m]-sl;
	int rr=rgt[m]-sr;
	if (ll) if (!solve(l,m-1,sl,rgt[m])) return false;
	if (rr) if (!solve(m+1,r,lft[m],sr)) return false;
	return true;
}

int find_best(int n) {
	memset(lft,-1,sizeof(lft));
	memset(rgt,-1,sizeof(rgt));

	while (ans==-1) {
		solve(0,n-1,0,0);
	}
	return ans;
}

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