Submission #389056

#	Time	Username	Problem	Language	Result	Execution time	Memory
389056		prvocislo	Gap (APIO16_gap)	C++17	49.72 / 100	109 ms	7784 KiB

gap

#include "gap.h"
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <iomanip>
typedef long long ll;
using namespace std;

// MinMax(, , &, &);
ll best;
void upd(ll x)
{
	best = max(best, x);
}
long long findGap1(int N)
{
	ll mini = -1, maxi = 1e18 + 79;
	vector<ll> v(N);
	for (int l = 0, r = N - 1; l <= r; l++, r--)
	{
		mini++, maxi--;
		MinMax(mini, maxi, &mini, &maxi);
		v[l] = mini;
		v[r] = maxi;
	}
	ll ans = 0;
	for (int i = 0; i < N - 1; i++) ans = max(ans, v[i + 1] - v[i]);
	return ans;
}
long long findGap(int T, int N)
{
	if (T == 1)return findGap1(N);
	ll mini = -1, maxi = 1e18; best = 1;
	set<ll> s;
	set<pair<ll, pair<ll, ll> >, greater<pair<ll, pair<ll, ll> >> > pq;
	MinMax(mini, maxi, &mini, &maxi);
	s.insert({ mini, maxi });
	pq.insert({ maxi - mini, {mini, maxi} });
	while (!pq.empty())
	{
		ll dist = pq.begin()->first;
		if (dist <= best) return best;
		mini = pq.begin()->second.first;
		maxi = pq.begin()->second.second;
		if (mini + 1 == maxi) break;
		if (mini + 2 == maxi)
		{
			ll a;
			MinMax(mini + 1, maxi - 1, &a, &a);
			if (a == -1) upd(2);
			else upd(1);
			break;
		}
		pq.erase(pq.begin());
		ll m1 = (mini + maxi) / 2, m2 = (mini + maxi) / 2 + 1;
		ll mi1, mx1, mi2, mx2;
		MinMax(mini + 1, m1, &mi1, &mx1);
		MinMax(m2, maxi - 1, &mi2, &mx2);
		if (mi1 != -1) s.insert(mi1), s.insert(mx1);
		if (mi2 != -1) s.insert(mi2), s.insert(mx2);
		upd(*next(s.find(mini)) - mini);
		upd(maxi - *prev(s.find(maxi)));
		if (mx1 != -1 && mi2 != -1) upd(mi2 - mx1);
		pq.insert({ mx1 - mi1, {mi1, mx1} });
		pq.insert({ mx2 - mi2, {mi2, mx2} });
	}
	return best;
}

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