Submission #720039

#	Time	Username	Problem	Language	Result	Execution time	Memory
720039		Forested	Gap (APIO16_gap)	C++17	100 / 100	63 ms	1076 KiB

gap

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

long long findGap(int t, int n) {
	if (t == 1) {
		long long ans = 0;
		long long pmn = -1, pmx = 1000000000000000001, mn = -1, mx = -1;
		for (int i = 0; i < (n + 1) / 2; ++i) {
			MinMax(pmn + 1, pmx - 1, &mn, &mx);
			if (i != 0) {
				ans = std::max({ans, mn - pmn, pmx - mx});
			}
			pmn = mn;
			pmx = mx;
		}
		ans = std::max(ans, pmx - pmn);
		return ans;
	}
	long long mn = -1, mx = -1;
	MinMax(0, 1000000000000000000, &mn, &mx);
	long long l = mn, h = mx;
	long long w = (h - l + n - 1) / n;
	long long cur = l + 1, pmx = l, ans = 0;
	while (cur <= h) {
		MinMax(cur, cur + w - 1, &mn, &mx);
		if (mn != -1) {
			if (pmx != -1) {
				ans = std::max(ans, mn - pmx);
			}
			pmx = mx;
		}
		cur += w;
	}
	return ans;
}

• Subtask 1: 30 / 30
• Subtask 2: 70 / 70