Submission #1101327

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

Compilation message (stderr)

gap.cpp: In instantiation of 'findGap(int, int)::<lambda(auto:23, long long int, long long int)> [with auto:23 = findGap(int, int)::<lambda(auto:23, long long int, long long int)>]':
gap.cpp:19:21:   required from here
gap.cpp:10:26: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   10 |    if (l > r || a.size() == N) return;
      |                 ~~~~~~~~~^~~~

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