Submission #1232650

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232650		Hamed_Ghaffari	The Big Prize (IOI17_prize)	C++20	100 / 100	14 ms	2052 KiB

prize

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

using pii = pair<int, int>;

#define X first
#define Y second

const int MXN = 2e5+5;

int loli;
pii cache[MXN];

pii query(int i) {
	if(cache[i].X!=-1) return cache[i];
	vector<int> tmp = ask(i);
	cache[i] = {tmp[0], tmp[1]};
	if(cache[i].X+cache[i].Y==0) throw i;
	return cache[i];
}

void rec(int l, int r, int cl, int cr) {
	if(l>r) return;
	for(int i=0; i<=r-l; i++) {
		int mid=(l+r)>>1, ml=mid-(i>>1), mr = mid+((i+1)>>1);
		mid = (i&1) ? mr : ml;
		pii x = query(mid);
		if(x.X+x.Y==loli) {
			int ccl = (i&1) ? mr-ml : 0, ccr = (i&1) ? 0 : mr-ml;
			if(x.X-ccl>cl) rec(l, ml-1, cl, ccl+x.Y);
			if(x.Y-ccr>cr) rec(mr+1, r, x.X+ccr, cr);
			return;
		}
	}
}

int find_best(int n) {
	fill(cache, cache+n, pii(-1, -1));
	try {
		int pos=0;
		for(int i=0; i<sqrt(n)+30 && i<n && loli<27; i++) {
			pii x = query(i);
			if(x.X+x.Y>loli) {
				loli = x.X+x.Y;
				pos = i;
			}
		}
		rec(pos, n-1, pos, 0);
	}
	catch(int ans) {
		return ans;
	}
	return 0;
}

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