답안 #389056

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
389056	2021-04-13T14:55:37 Z	prvocislo	Gap (APIO16_gap)	C++17	49.7181 / 100	109 ms	7784 KB

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.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	200 KB	Output is correct
2	Correct	1 ms	200 KB	Output is correct
3	Correct	1 ms	200 KB	Output is correct
4	Correct	1 ms	200 KB	Output is correct
5	Correct	1 ms	200 KB	Output is correct
6	Correct	1 ms	200 KB	Output is correct
7	Correct	0 ms	200 KB	Output is correct
8	Correct	1 ms	200 KB	Output is correct
9	Correct	1 ms	256 KB	Output is correct
10	Correct	1 ms	240 KB	Output is correct
11	Correct	1 ms	328 KB	Output is correct
12	Correct	1 ms	328 KB	Output is correct
13	Correct	1 ms	456 KB	Output is correct
14	Correct	1 ms	328 KB	Output is correct
15	Correct	1 ms	328 KB	Output is correct
16	Correct	11 ms	712 KB	Output is correct
17	Correct	11 ms	628 KB	Output is correct
18	Correct	12 ms	680 KB	Output is correct
19	Correct	12 ms	600 KB	Output is correct
20	Correct	9 ms	584 KB	Output is correct
21	Correct	44 ms	1824 KB	Output is correct
22	Correct	47 ms	1824 KB	Output is correct
23	Correct	46 ms	1856 KB	Output is correct
24	Correct	59 ms	1828 KB	Output is correct
25	Correct	40 ms	1828 KB	Output is correct
26	Correct	48 ms	1820 KB	Output is correct
27	Correct	44 ms	1816 KB	Output is correct
28	Correct	44 ms	1828 KB	Output is correct
29	Correct	45 ms	1804 KB	Output is correct
30	Correct	36 ms	1864 KB	Output is correct
31	Correct	1 ms	200 KB	Output is correct
32	Correct	1 ms	200 KB	Output is correct

Subtask #2

19.7180885677 / 70.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	200 KB	Output is correct
2	Correct	1 ms	200 KB	Output is correct
3	Correct	2 ms	200 KB	Output is correct
4	Correct	0 ms	200 KB	Output is correct
5	Partially correct	1 ms	200 KB	Partially correct
6	Partially correct	1 ms	200 KB	Partially correct
7	Partially correct	1 ms	200 KB	Partially correct
8	Partially correct	1 ms	200 KB	Partially correct
9	Partially correct	1 ms	200 KB	Partially correct
10	Correct	1 ms	200 KB	Output is correct
11	Partially correct	1 ms	328 KB	Partially correct
12	Partially correct	2 ms	328 KB	Partially correct
13	Partially correct	1 ms	328 KB	Partially correct
14	Partially correct	1 ms	328 KB	Partially correct
15	Partially correct	2 ms	328 KB	Partially correct
16	Partially correct	18 ms	936 KB	Partially correct
17	Partially correct	13 ms	908 KB	Partially correct
18	Partially correct	12 ms	968 KB	Partially correct
19	Partially correct	13 ms	900 KB	Partially correct
20	Correct	5 ms	456 KB	Output is correct
21	Partially correct	53 ms	3104 KB	Partially correct
22	Partially correct	53 ms	3084 KB	Partially correct
23	Partially correct	55 ms	3056 KB	Partially correct
24	Partially correct	52 ms	3108 KB	Partially correct
25	Partially correct	109 ms	7784 KB	Partially correct
26	Partially correct	57 ms	3072 KB	Partially correct
27	Partially correct	53 ms	3104 KB	Partially correct
28	Partially correct	53 ms	3136 KB	Partially correct
29	Partially correct	57 ms	3104 KB	Partially correct
30	Correct	13 ms	980 KB	Output is correct
31	Correct	1 ms	200 KB	Output is correct
32	Correct	1 ms	272 KB	Output is correct