Submission #1101329

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101329		huyngo	Gap (APIO16_gap)	C++17	86.31 / 100	50 ms	4220 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 x, y;
	MinMax(0, 1e18, &x, &y);
	ll step = (y - x) / (N - 1);
	ll res = step, prv = x;
	++x;
	for (ll u, v; x <= y; ) {
		MinMax(x, x + step, &u, &v);
		if (u != -1) {
			res = max(res, u - prv);
			prv = v;
			x = v + 1;
		}
		else
			x += step;
	}
	return res;
}

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