Submission #1101335

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101335		huyngo	Gap (APIO16_gap)	C++17	100 / 100	49 ms	4116 KiB

gap

#include "gap.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long

long long findGap(int T, int N) {
	if (T == 1) {
		vector<ll> a;
		auto calc = [&](auto self, ll l, ll r) -> void {
			if (l > r || (int)a.size() == N) return;
			ll x, y;
			MinMax(l, r, &x, &y);
			if (x != -1)
				a.push_back(x);
			if (y != x)
				a.push_back(y);
			self(self, x + 1, y - 1);
			};
		calc(calc, 0, 1e18);
		sort(a.begin(), a.end());
		ll res = a[1] - a[0];
		for (int i = 2; i < N; ++i)
			res = max(res, a[i] - a[i - 1]);
		return res;
	}

	ll mn, mx;
	MinMax(1, 1e18, &mn, &mx);
	ll step = (mx - mn) / (N - 1);
	ll ans = step, x, y, l = mn, i;
	for (i = mn; i + step < mx; i += step + 1) {
		MinMax(i, i + step, &x, &y);
		if (x != -1) {
			ans = max(ans, x - l);
			l = y;
		}
	}
	MinMax(i, mx, &x, &y);
	if (x != -1) ans = max(ans, x - l);
	return ans;
}

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