Submission #24991

#	Time	Username	Problem	Language	Result	Execution time	Memory
24991		gabrielsimoes	Gap (APIO16_gap)	C++14	100 / 100	76 ms	4900 KiB

gap

#include "gap.h"
#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long ll;
const ll MIN = 0, MAX = 1000000000000000000;

ll solve1(int n) {
	ll v[n+1];
	int i = 1, k = n;
	ll mn = MIN, mx = MAX;
	while (i <= k) {
		MinMax(mn, mx, v+i, v+k);
		mn = v[i++]+1;
		mx = v[k--]-1;
	}

	ll ret = 1;
	for (int i = 1; i < n; i++)
		ret = max(ret, v[i+1] - v[i]);
	return ret;
}

ll solve2(int n) {
	ll cur, lim;
	MinMax(MIN, MAX, &cur, &lim);
	ll ans = (lim - cur + 1)/n, test, l, r;
	while (cur < lim && cur + ans < lim) {
		test = ans + 2;
		do {
			MinMax(cur+1, cur+test, &l, &r);
			test = test*2 + 2;
		} while (l == -1);
		ans = max(ans, l - cur);
		cur = r;
	}
	return ans;
}

ll findGap(int t, int n)
{
	return (t == 1 || n <= 8) ? solve1(n) : solve2(n);
}

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