Submission #33911

#	Time	Username	Problem	Language	Result	Execution time	Memory
33911		imeimi2000	The Big Prize (IOI17_prize)	C++14	100 / 100	33 ms	3724 KiB

prize

#include "prize.h"
#include <algorithm>

using namespace std;
typedef pair<int, int> pi;

//1 + 4 + 21 + 446 = 472
const int MAXDIA = 473;
int n, m, g, r;

pi save[200000];
pi question(int i) {
	if (save[i] != pi(0, 0)) return save[i];
	vector<int> ret = ask(i);
	if (ret[0] == 0 && ret[1] == 0) throw i;
	return save[i] = pi(ret[0], ret[1]);
}

void bsearch(int s, int e, int lc, int rc, int c) {
	if (c == 0) return;
	if (c == e - s + 1) {
		for (int i = s; i <= e; ++i) question(i);
		return;
	}
	int md = (s + e) / 2;
	int l = md + 1, r = md, p;
	for (int i = 0; i <= e - s; ++i) {
		if (i % 2 == 0) p = --l;
		else p = ++r;
		pi ret = question(p);
		int ls = ret.first - lc - (i % 2 == 0 ? 0 : r - l);
		if (ret.first + ret.second == m) {
			bsearch(s, l - 1, lc, rc + c - ls, ls);
			bsearch(r + 1, e, lc + ls + r - l, rc, c - ls - r + l);
			break;
		}
	}
}

int find_best(int N) {
	n = N;
	if (n < MAXDIA) {
		for (int i = 0; i < n; ++i) {
			vector<int> ret = ask(i);
			if (ret[0] == 0 && ret[1] == 0) return i;
		}
	}
	g = n / MAXDIA;
	r = n - MAXDIA * g;

	try {
		int i, s, e;
		for (i = 0, s = 0; i < MAXDIA; ++i) {
			if (i < r) e = s + g;
			else e = s + g - 1;
			pi ret = question(e);
			m = max(m, ret.first + ret.second);
			s = e + 1;
		}
		int lc = 0;
		for (i = 0, s = 0; i < MAXDIA; ++i) {
			if (i < r) e = s + g;
			else e = s + g - 1;
			pi ret = question(e);
			int j = e;
			int ct = 0;
			while (s < j && ret.first + ret.second != m) {
				ret = question(--j);
			}
			bsearch(s, j - 1, lc, ret.second, ret.first - lc);
			lc = e - j + ret.first;
			s = e + 1;
		}
	}
	catch (int i) {
		return i;
	}

	return 0;
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:66:8: warning: unused variable 'ct' [-Wunused-variable]
    int ct = 0;
        ^

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