Submission #1164911

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164911		KickingKun	Gap (APIO16_gap)	C++20	46.81 / 100	59 ms	3448 KiB

gap

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

#define ll long long

ll ans = 1;

vector <ll> dnc(ll l, ll r, ll need) {
	if (r + 1 - (l - 1) <= ans) return {};
	
	need = min(need, r - l + 1);
	if (need <= 0) return {};
	if (need <= 2) {
		vector <ll> res;
		ll x, y; MinMax(l, r, &x, &y);
		if (x != -1) res.emplace_back(x);
		if (x < y) res.emplace_back(y), ans = max(ans, y - x);
		return res;
	}
	
	ll mid = (l + r) >> 1;
	ll a, b, c, d; 
	MinMax(l, mid, &a, &b);
	MinMax(mid + 1, r, &c, &d);
	
	vector <ll> res;
	if (a != -1) res.emplace_back(a);
	if (a < b) res.emplace_back(b);
	if (c != -1) res.emplace_back(c);
	if (c < d) res.emplace_back(d);
	
	if (a != -1) {
		vector <ll> A = dnc(a + 1, b - 1, need - res.size());
		for (ll &x: A) res.emplace_back(x);
	}
	if (c != -1) {
		vector <ll> B = dnc(c + 1, d - 1, need - res.size());
		for (ll &x: B) res.emplace_back(x);
	}
	
	sort (res.begin(), res.end());
	for (int i = 1; i < res.size(); i++)
		ans = max(ans, res[i] - res[i - 1]);
	return res;
}

ll findGap(int T, int N) {
	if (T == 1) {
		vector <ll> A, B;
		ll l = 0, r = 1e18;
		while (l <= r && A.size() + B.size() < N) {
			ll x, y; MinMax(l, r, &x, &y);
			if (x == -1) break;
			A.emplace_back(x);
			if (x < y) B.emplace_back(y);
			l = x + 1, r = y - 1;
		}
		for (int i = B.size() - 1; i > -1; i--)
			A.emplace_back(B[i]);
		
		ll ans = 0;
		for (int i = 1; i < A.size(); i++)
			ans = max(ans, A[i] - A[i - 1]);
		return ans;
	}
	
	else {
		vector <ll> res = dnc(0, 1e18, N);
		return ans;
	}
}

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