Submission #40875

#	Time	Username	Problem	Language	Result	Execution time	Memory
40875		gabrielsimoes	Gap (APIO16_gap)	C++14	100 / 100	88 ms	2284 KiB

gap

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

typedef long long ll;
const ll INF = 1000000000000000000;

ll findGap(int T, int N) {
	if (T == 1) {
		ll v[N], mn = -1, mx = INF+1;
		for (int i = 0, k = N-1; i <= k; i++, k--) {
			MinMax(mn+1, mx-1, &v[i], &v[k]);
			mn = v[i];
			mx = v[k];
		}

		ll ans = 0;
		for (int i = 1; i < N; i++) {
			ans = max(ans, v[i] - v[i-1]);
		}

		return ans;
	} else {
		ll total_min, total_max;
		MinMax(0, INF, &total_min, &total_max);

		ll ans = (total_max - total_min + ll(N - 1))/ll(N);
		ll cur = total_min;
		while(cur < total_max) {
			ll mn = -1, mx = -1;
			ll step = ans;
			while (mn == -1) {
				MinMax(cur+1, cur+step+1, &mn, &mx);
				step += ans;
			}

			ans = max(ans, mn - cur);
			cur = mx;
		}

		return ans;
	}
}

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