제출 #1271512

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1271512		cmiuc	Gap (APIO16_gap)	C++20	100 / 100	45 ms	1952 KiB

gap

#include <iostream>
#include "gap.h"

using namespace std;
long long Arr[1<<17], ans;

long long solve1(int n){
	Arr[0] = -1;
	Arr[n + 1] = 1.1e18;
	for (int i=1;i <= n - i + 1;i++)
		MinMax(Arr[i - 1] + 1, Arr[n - i + 2] - 1, &Arr[i], &Arr[n - i + 1]);

	for (int i=2;i<=n;i++)
		ans = max(ans, Arr[i] - Arr[i-1]);
	return ans;
}

long long findGap(int t, int n){
	if (t == 1)
		return solve1(n);
	long long Mn, Mx, A, B, inf = 1e18, lst;

	MinMax(0, inf, &Mn, &Mx);
	lst = Mn;
	long long Gap = (Mx - Mn + n - 2) / (n - 1);

	while (1){
		MinMax(Mn + 1, Mn + Gap, &A, &B);
		if (A != -1){
			Mn = Mn + Gap;
			Gap = max(Gap, A - lst);
			lst = B;
		}
		else
			Mn = Mn + Gap;
		if (B == Mx)
			break;
	}
	return Gap;
}

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