Submission #986768

#	Time	Username	Problem	Language	Result	Execution time	Memory
986768		siewjh	Gap (APIO16_gap)	C++17	30 / 100	45 ms	2144 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 (int i = 0; i < N - 1; i++){
			ll mnh, mxh; MinMax(mn + gap * i + 1, min(mn + gap * (i + 1), mx), &mnh, &mxh);
			if (mnh == -1) continue;
			ans = max(ans, mnh - prv);
			prv = mxh;
		}
		return ans;
	}
}

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