제출 #986778

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

gap

#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll cdiv(ll a, ll b){
	return (a + b - 1) / b;
}
ll findGap(int T, int N){
	if (T == 1){
		vector<ll> vec(N);
		ll lv = 0, rv = 1e18, ans = 0;
		for (int l = 0, r = N - 1; l <= r; l++, r--){
			MinMax(lv, rv, &vec[l], &vec[r]);
			lv = vec[l] + 1; rv = vec[r] - 1;
		}
		for (int i = 1; i < N; i++) ans = max(ans, vec[i] - vec[i - 1]);
		return ans;
	}
	else{
		ll mn, mx; MinMax(0, 1e18, &mn, &mx);
		ll gap = cdiv(mx - mn, N - 1), prv = mn, ans = 0;
		for (ll x = mn + 1; x <= mx; x += gap){
			ll mnh, mxh; MinMax(x, min(x + gap - 1, mx), &mnh, &mxh);
			if (mnh == -1) continue;
			ans = max(ans, mnh - prv);
			prv = mxh;
		}
		return ans;
	}
}

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