제출 #251438

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
251438		atoiz	Gap (APIO16_gap)	C++14	70 / 100	59 ms	1272 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 maxGap = 1;
	if (T == 2) {
		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;
			}
		}
	} else {
		long long L, R;
		long long X = 1e18;
		MinMax(0, X, &L, &R);
		while (L < R) {
			long long A, B;
			MinMax(L + 1, R - 1, &A, &B);
			if (A == -1) {
				if (maxGap < R - L) maxGap = R - L;
				break;
			}
			if (maxGap < A - L) maxGap = A - L;
			if (maxGap < R - B) maxGap = R - B;
			L = A, R = B;
		}
	}
	return maxGap;
}

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