Submission #1278390

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278390		Lithanium	Gap (APIO16_gap)	C++20	0 / 100	2120 ms	589824 KiB

gap

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

using ll = long long;

long long findGap(int T, int N)
{
	if (T == 1) {
		// Step 1, find A1 and An
		ll l, r;
		MinMax(0, 1e18, &l, &r);
		ll sz = (r-l+N-2)/(N-1);
		vector<ll> relevant = {l, r};
		for (ll i = l+1; i < r; i += sz) {
			// l = i, r = i+sz-1;
			ll l1, r1;
			MinMax(i, i+sz-1, &l1, &r1);
			if (l1 != -1) relevant.push_back(l1), relevant.push_back(r1);
		}
		sort(relevant.begin(), relevant.end());
		ll ans = 0;
		for (int i = 0; i+1 < relevant.size(); i ++) ans = max(ans, relevant[i+1] - relevant[i]);
		return ans;
	}
	ll l, r;
	MinMax(0, 1e18, &l, &r);
	vector<ll> has;
	while (l < r) {
		has.push_back(l);
		has.push_back(r);
		MinMax(0, 1e18, &l, &r);
	}
	if (l != -1) has.push_back(l);
	sort(has.begin(), has.end());
	ll ans = 0;
	for (int i = 0; i+1 < has.size(); i ++) ans = max(ans, has[i+1] - has[i]);
	return ans;
}

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