Submission #63791

#	Time	Username	Problem	Language	Result	Execution time	Memory
63791		kingpig9	Gap (APIO16_gap)	C++11	100 / 100	110 ms	2280 KiB

gap

#include <bits/stdc++.h>
#include "gap.h"

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 1e5 + 10;

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))

int N;
ll A[MAXN];

ll findGap (int subtask, int nnn) {
	N = nnn;
	ll ans = 0;
	if (subtask == 1) {
		for (int i = 1, j = N; i <= j; i++, j--) {
			ll mn, mx;
			if (i == 1) {
				mn = 0;
				mx = 1e18;
			} else {
				mn = A[i - 1] + 1;
				mx = A[j + 1] - 1;
			}
			MinMax(mn, mx, &mn, &mx);
			A[i] = mn;
			A[j] = mx;
		}

		for (int i = 2; i <= N; i++) {
			ans = max(ans, A[i] - A[i - 1]);
		}
	} else {
		ll a1, an;
		MinMax(0, 1e18, &a1, &an);
		ll gap = (an - a1 + (N - 2)) / (N - 1);	//gap at least this big
		ll pval = a1;
		for (ll lt = a1 + 1, rt = a1 + gap; lt <= an; lt += gap, rt += gap) {
			ll imn, imx;	//interval mn, mx
			MinMax(lt, rt, &imn, &imx);
			if (imn != -1) {
				ans = max(ans, imn - pval);
				pval = imx;
			}
		}
		ans = max(ans, an - pval);
	}
	return ans;
}

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