Submission #251441

#	Time	Username	Problem	Language	Result	Execution time	Memory
251441		atoiz	Gap (APIO16_gap)	C++14	100 / 100	59 ms	1172 KiB

gap

#include "gap.h"
#include <cassert>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <iostream>

using namespace std;

long long findGap(int T, int N)
{
	long long L, R;
	long long X = 1e18;
	MinMax(0, X, &L, &R);
	long long maxGap = (R - L + N - 2) / (N - 1);
	if (N == 2) return R - L;
	if (T == 2) {
		while (R - L > maxGap) {
			long long gap = maxGap;
			while (true) {
				long long A, B;
				MinMax(L + 1, L + gap + 1, &A, &B);
				if (A == -1) { gap *= 2; continue; }
				if (maxGap < A - L) maxGap = A - L;
				L = B;
				break;
			}
		}
	} else {
		for (int i = N - 2; i > 0; i -= 2) {
			long long A, B;
			MinMax(L + 1, R - 1, &A, &B);
			if (maxGap < A - L) maxGap = A - L;
			if (maxGap < R - B) maxGap = R - B;
			L = A, R = B;
		}
		if (maxGap < R - L) maxGap = R - L;
	}
	return maxGap;
}

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