Submission #101884

#	Time	Username	Problem	Language	Result	Execution time	Memory
101884		KCSC	Gap (APIO16_gap)	C++14	100 / 100	73 ms	3064 KiB

gap

#ifndef HOME
	#include "gap.h"
#endif

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

#ifdef HOME
const int DIM = 100005;

long long arr[DIM]; int N;

void MinMax(long long a, long long b, long long *mn, long long *mx) {
	mn = 1LL << 60, mx = -1LL << 60;
	for (int i = 1; i <= N; ++i) {
		if (arr[i] >= a and arr[i] <= b) {
			mn = min(mn, arr[i]); mx = max(mx, arr[i]); } } 
	if (mn > mx) {
		mn = mx = -1; } }
#endif

long long findGap(int t, int n) {
	long long mn, mx, ans = 0;
	MinMax(0, 1LL << 60, &mn, &mx);
	if (t == 1) {
		for (int i = 1; i < (n + 1) / 2; ++i) {
			long long mn2, mx2;
			MinMax(mn + 1, mx - 1, &mn2, &mx2);
			ans = max(ans, mn2 - mn); ans = max(ans, mx - mx2);
			mn = mn2; mx = mx2; }
		ans = max(ans, mx - mn); }
	else {
		long long sz = (mx - mn + n - 1) / n, ls = mn;
		for (long long st = mn + 1, en = mn + sz, i = 1; i <= n; st += sz, en += sz, ++i) {
			if (en > mx - 1) { en = mx - 1; }
			if (st > en) { break; }
			long long mn2, mx2;
			MinMax(st, en, &mn2, &mx2);
			if (mn2 != -1) {
				ans = max(ans, mn2 - ls); ls = mx2; } }
		ans = max(ans, mx - ls); }
	return ans; }

#ifdef HOME
int main(void) {
	freopen("gap.in", "r", stdin);
	freopen("gap.out", "w", stdout);
	int n; cin >> n; N = n;
	for (int i = 1; i <= n; ++i) {
		cin >> arr[i]; }
	sort(arr + 1, arr + n + 1);
	cout << findGap(1, n) << " " << findGap(2, n) << endl;
	return 0; }
#endif

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