제출 #1367543

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1367543		Nxmkxing	Gap (APIO16_gap)	C++20	83.51 / 100	31 ms	1936 KiB

gap

#include "gap.h"
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pll = pair<long long, long long>;
const ll inf = 2e18;

const int N = 1e5 + 10;
ll n, a[N];

long long findGap(int T, int N) {
	n = N;
	if (T == 1) {
		a[0] = -inf, a[n+1] = inf;
		int l = 1, r = n;
		while (l <= r) {
			ll mn, mx;
			MinMax(a[l-1] + 1, a[r+1] - 1, &mn, &mx);
			a[l] = mn, a[r] = mx;
			l++, r--;
		}
		ll best = 0;
		for (int i = 2; i <= n; i++) {
			best = max(best, a[i] - a[i-1]);
		}
		return best;
	}
	ll mn, mx;
	MinMax(-inf, inf, &mn, &mx);
	ll goodGab = (mx - mn - 1) / (n - 1);
	ll ans = goodGab;
	pll beforeBlock = {-1, -1};
	for (ll l = mn, r = mn + goodGab; l <= mx; l += goodGab + 1, r += goodGab + 1) {
		pll nowBlock;
		MinMax(l, r, &nowBlock.first, &nowBlock.second);
		if (nowBlock.first == -1) continue;
		if (beforeBlock.first != -1) ans = max(ans, nowBlock.first - beforeBlock.second);
		beforeBlock = nowBlock;
	}
	return ans;
}

• 서브태스크 1: 30 / 30
• 서브태스크 2: 53.5083 / 70