Submission #1209788

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209788		k1r1t0	Gap (APIO16_gap)	C++20	100 / 100	40 ms	1148 KiB

gap

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const ll INF = (ll)(1e18);

void MinMax(ll s, ll t, ll *mn, ll *mx);

ll findGap(int T, int N) {
	if (T == 1) {
		ll a, b;
		MinMax(0, INF, &a, &b);
		ll ans = 0;
		while (a + 1 < b) {
			N -= 2;
			if (N == 0) break;
			ll c, d;
			MinMax(a + 1, b - 1, &c, &d);
			ans = max(ans, c - a);
			ans = max(ans, b - d);
			a = c;
			b = d;
		}
		ans = max(ans, b - a);
		return ans;
	}
	ll first, last;
	MinMax(0, INF, &first, &last);
	ll pos = first, ans = 1, base = (last - first + N - 2) / (N - 1);
	while (pos != last) {
		ll cur = base;
		while (true) {
			ll a, b;
			MinMax(pos + 1, pos + cur, &a, &b);
			if (a == -1) {
				base = cur;
				cur *= 2;
				continue;
			}
			ans = max(ans, a - pos);
			pos = b;
			break;
		}
	}
	ans = max(ans, last - pos);
	return ans;
}

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