Submission #94529

#	Time	Username	Problem	Language	Result	Execution time	Memory
94529		hugo_pm	Gap (APIO16_gap)	C++14	100 / 100	61 ms	1916 KiB

gap

#include "gap.h"
#include <vector>
#include <iostream>
using namespace std;

typedef long long llg;

vector<llg> a;

llg s1(int n)
{
	a.resize(n);
	llg x = 0, y = (llg)(1e18);
	int d = 0, f = n-1;
	while (d <= f) {
		MinMax(x, y, &x, &y);
		a[d] = x;
		a[f] = y;
		++x; ++d;
		--y; --f;
	}
	llg r = 0;
	for (int i = 0; i < (n-1); ++i) {
		r = max(r, a[i+1] - a[i]);
	}
	return r;
}

llg s2(int n)
{
	llg amin, amax;
	MinMax(0, (llg)(1e18), &amin, &amax);
	llg totSize = amax-amin+1-2;
	llg sizeBloc = totSize/(n-1);
	llg deb = 0, fin = amin;
	llg ans = 0, der = amin;

	for (int iBloc = 0; iBloc < (n-1); ++iBloc) {
		deb = fin+1;
		fin = deb+sizeBloc-1;
		if (iBloc <= (totSize) % (n-1)) ++fin;
		llg xl, xr;
		MinMax(deb, fin, &xl, &xr);
		if (xl != -1) {
			if (der != -1) ans = max(ans, xl - der);
			der = xr;
		}
	}
	ans = max(ans, amax - der);
	return ans;
}

llg findGap(int t, int n)
{
	if (t == 1) return s1(n);
	else return s2(n);
}

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