Submission #1101316

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101316		huyngo	Gap (APIO16_gap)	C++17	33.55 / 100	43 ms	4100 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, res = 1;
	MinMax(0, 1e18, &x, &y);
	while (true) {
		// find furest from x where [x+1, m] = -1
		if (x >= y || x + res >= y) break;
		ll u, v;
		MinMax(x + 1, x + res, &u, &v);
		if (u != -1) {
			x = v;
			continue;
		}
		ll l = x + res, r = y, sf = l;
		while (l <= r) {
			ll m = (l + r) / 2;
			MinMax(x + 1, m, &u, &v);
			if (u == -1) {
				l = m + 1;
				sf = max(sf, m);
				res = max(res, m - x + 1);
			}
			else
				r = m - 1;
		}
		x = sf + 1;
	}
	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: 3.5526543391 / 70