Submission #35522

#	Time	Username	Problem	Language	Result	Execution time	Memory
35522		kdh9949	The Big Prize (IOI17_prize)	C++14	100 / 100	49 ms	4360 KiB

prize

#include "prize.h"
using namespace std;

using pii = pair<int, int>;
#define X first
#define Y second

const int MN = 200000, MC = 500;
int cnt, tot, chk[MN], dia;
pii dat[MN];

pii get(int x){
	if(chk[x]) return dat[x];
	chk[x] = 1;
	vector<int> v = ask(x);
	dat[x] = pii(v[0], v[1]);
	if(v[0] + v[1] == 0) dia = x;
	tot = max(tot, v[0] + v[1]);
	return dat[x];
}

void pre(int s, int e){
	if(cnt == MC) return;
	int m = (s + e) / 2;
	get(m); cnt++;
	if(s == e) return;
	pre(s, m);
	pre(m + 1, e);
}

void dnc(int s, int e, int lc, int mc, int rc){
	if(mc == 0) return;
	if(s == e){
		get(s);
		return;
	}
	int m = (s + e) / 2;
	int mmc = 0;
	for(int i = m; i >= s; i--){
		pii t = get(i);
		if(t.X + t.Y == tot){
			mmc += t.X - lc;
			break;
		}
		mmc++;
	}
	dnc(s, m, lc, mmc, rc + mc - mmc);
	dnc(m + 1, e, lc + mmc, mc - mmc, rc);
}

int find_best(int n) {
	pre(0, n - 1);
	dnc(0, n - 1, 0, tot, 0);
	return dia;
}

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