제출 #561500

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
561500		hollwo_pelw	Gap (APIO16_gap)	C++17	100 / 100	47 ms	1104 KiB

gap

#include <bits/stdc++.h>
#include "gap.h"
 
using namespace std;
 
long long solve(int N) {
	long long l, r, res = 0;
	MinMax(0, 1e18, &l, &r);
 
	for (int i = 1; i <= (N - 1) / 2; i++) {
		long long nl, nr;
		MinMax(l + 1, r - 1, &nl, &nr);
 
		res = max(res, nl - l), l = nl;
		res = max(res, r - nr), r = nr;
	}
 
	return max(res, r - l);
}
 
long long findGap(int T, int N) {
	if (T == 1)
		return solve(N);
 
	long long l, r;
	MinMax(0, 1e18, &l, &r);
 
	long long res = (r - l - 1) / (N - 1) + 1;
 
	for (long long nl, nr; l < r; l = nr) {
		MinMax(l + 1, l + res, &nl, &nr);
		if (nr != -1) continue ;
	
		MinMax(l + 1, l + (res + 1) * 2, &nl, &nr);
		while (nl == -1) {
			res = (res + 1) * 2 + 1;
			MinMax(l + 1, l + (res + 1) * 2, &nl, &nr);
		}
		res = nl - l;
	}
 
	return res;
}

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