Submission #251437

#	Time	Username	Problem	Language	Result	Execution time	Memory
251437		atoiz	Gap (APIO16_gap)	C++14	70 / 100	61 ms	1196 KiB

gap

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

using namespace std;

long long maxGap = 1;
long long findGap(int T, int N)
{
	long long L, R;
	long long X = 1e18;
	MinMax(0, X, &L, &R);
	maxGap = (R - L + N - 2) / (N - 1);
	if (N == 2) return R - L;
	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;
		}
	}
	return maxGap;
}

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