Submission #566475

#	Time	Username	Problem	Language	Result	Execution time	Memory
566475		Temmie	The Big Prize (IOI17_prize)	C++17	100 / 100	57 ms	5148 KiB

prize

//#include "public_a/cpp/prize.h"
#include "prize.h"

#include <bits/stdc++.h>

int find_best(int n) {
	std::vector <std::vector <int>> dp(n);
	dp[0] = ask(0);
	int mx = dp[0][0] + dp[0][1];
	for (int last = -1, i = 0; ; i++) {
		int l = 0, r = n - 1;
		while (l < r) {
			int mid = (l + r) >> 1;
			if (mid <= last) {
				l = mid + 1;
				continue;
			}
			if (dp[mid].empty()) {
				dp[mid] = ask(mid);
			}
			if (!(dp[mid][0] + dp[mid][1])) {
				return mid;
			}
			if (dp[mid][0] + dp[mid][1] > mx) {
				mx = dp[mid][0] + dp[mid][1];
				l = 0, r = n - 1;
				continue;
			}
			if (mid <= last || (dp[mid][0] + dp[mid][1] == mx && dp[mid][0] < i)) {
				l = mid + 1;
			} else {
				r = mid;
			}
		}
		if (dp[last = l].empty()) {
			dp[l] = ask(l);
		}
		if (!(dp[l][0] + dp[l][1])) {
			return l;
		}
	}
	assert(false);
	return 0;
}

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