Submission #252169

#	Time	Username	Problem	Language	Result	Execution time	Memory
252169		Berted	Gap (APIO16_gap)	C++14	100 / 100	76 ms	1960 KiB

gap

#include "gap.h"
#include <iostream>
#define ll long long

const ll MN = 0, MX = 1e18;

using namespace std;

ll ret = MN;
ll ar[100001];

ll findGap(int T, int N)
{
	if (T == 1)
	{
		ll L = MN, R = MX, k = 0;
		for (int i = N; i > 0; i -= 2)
		{
			MinMax(L, R, &ar[k], &ar[N - 1 - k]);
			L = ar[k] + 1;
			R = ar[N - 1 - k] - 1;
			k++;
		}
		for (int i = 1; i < N; i++) {ret = max(ret, ar[i] - ar[i - 1]);}
	}
	else
	{
		ll lf, rg, gp;
		MinMax(MN, MX, &lf, &rg);
		ret = (rg - lf + N - 2) / (N - 1), gp = ret;
		ll pv = -1;
		for (ll i = lf; i <= rg; i += gp + 1)
		{
			ll t1, t2;
			MinMax(i, min(i + gp, rg), &t1, &t2);
			if (t1 != -1)
			{
				if (pv != -1) {ret = max(ret, t1 - pv);}
				pv = t2;
			}
		}
	}
	return ret;
}

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