제출 #1278393

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1278393		Lithanium	Gap (APIO16_gap)	C++20	100 / 100	49 ms	3320 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 == 2) {
		// 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;
	// cout << l << " " << r << "\n";
	int know = 2;
	while (l+1 <= r-1 and know < N) {
		has.push_back(l);
		has.push_back(r);
		ll a, b;
		MinMax(l+1, r-1, &a, &b);
		l = a, r = b;
		know += 2;
		// cout << l << " " << r << "\n";
	}
	if (l != -1) has.push_back(l);
	if (l != r) has.push_back(r);
	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: 30 / 30
• Subtask 2: 70 / 70