Submission #431872

#	Time	Username	Problem	Language	Result	Execution time	Memory
431872		rainboy	The Big Prize (IOI17_prize)	C++98	100 / 100	48 ms	324 KiB

prize

#include "prize.h"

#define K	500

using namespace std;

typedef vector<int> vi;

int max(int a, int b) { return a > b ? a : b; }

int lollipop;

int solve(int l, int r, int l_, int r_) {
	int m, i;

	if (l_ == r_)
		return -1;
	m = (l + r) / 2;
	for (i = m; i < r; i++) {
		vi a = ask(i);

		if (a[0] + a[1] == 0)
			return i;
		if (a[0] + a[1] == lollipop) {
			int i_;

			if ((i_ = solve(l, m, l_, a[0] - (i - m))) != -1)
				return i_;
			return solve(i + 1, r, a[0], r_);
		}
	}
	for (i = m - 1; i >= l; i--) {
		vi a = ask(i);

		if (a[0] + a[1] == 0)
			return i;
		if (a[0] + a[1] == lollipop)
			return solve(l, i, l_, a[0]);
	}
	return -1;
}

int find_best(int n) {
	int i;

	for (i = 0; i < n && i <= K; i++) {
		vi a = ask(i);

		if (a[0] + a[1] == 0)
			return i;
		lollipop = max(lollipop, a[0] + a[1]);
		if (lollipop > 100)
			return solve(i + 1, n, i, lollipop);
	}
	return solve(0, n, 0, lollipop);
}

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