Submission #1252344

#	Time	Username	Problem	Language	Result	Execution time	Memory
1252344		PlayVoltz	The Big Prize (IOI17_prize)	C++20	100 / 100	12 ms	1972 KiB

prize

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

#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second

int mx=0, ans=-1;
vector<pii> ooga;

pii query(int a){
	if (ooga[a].fi!=-1)return ooga[a];
	vector<int> res=ask(a);
	if (!(res[0]+res[1]))ans=a;
	return ooga[a]=mp(res[0], res[1]);
}

void dnc(int l, int r, int cl, int cr){
	if (l>r)return;
	for (int i=0; i<=r-l; ++i){
		int lm=(l+r)/2-i/2, rm=(l+r)/2+(i+1)/2, m=(i%2?rm:lm);
		pii res=query(m);
		if (ans!=-1)return;
		if (res.fi+res.se==mx){
			if (i%2){
				if (res.se>cr)dnc(rm+1, r, res.fi, cr);
				if (res.fi-rm+lm>cl)dnc(l, lm-1, cl, res.se+rm-lm);
			}
			else{
				if (res.fi>cl)dnc(l, lm-1, cl, res.se);
				if (res.se-rm+lm>cr)dnc(rm+1, r, res.fi+rm-lm, cr);
			}
			return;
		}
	}
}

int find_best(int n){
	if (n==1)return 0;
	ooga.resize(n, mp(-1, -1));
	int id=0;
	for (int i=0; i<sqrt(n)+30&&mx<27; ++i){
		pii res=query(i);
		if (ans!=-1)break;
		if (res.fi+res.se>mx)mx=res.fi+res.se, id=i;
	}
	dnc(id, n-1, id, 0);
	return ans;
}

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