Submission #1147245

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147245		yeediot	Gap (APIO16_gap)	C++20	100 / 100	40 ms	1864 KiB

gap

#include "gap.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
const ll inf = 1e18;
long long findGap(int t, int n)
{
	if(t == 1){
		ll mn, mx;
		MinMax(0, inf, &mn, &mx);
		vector<ll>a(n + 1);
		a[1] = mn, a[n] = mx;
		for(int i = 2; i * 2 - 1 <= n; i++){
			MinMax(a[i - 1] + 1, a[n - i + 2] - 1, &mn, &mx);
			a[i] = mn;
			a[n - i + 1] = mx;
		}
		ll ans = 0;
		for(int i = 2; i <= n; i++){
			ans = max(ans, a[i] - a[i - 1]);
		}
		return ans;
	}
	else{
		ll mn, mx;
		MinMax(0, inf, &mn, &mx);
		ll siz = (mx - mn + n - 2) / (n - 1);
		ll prv = mn, ans = 0;
		for(ll i = mn + 1; i <= mx; i += siz){
			ll r = min(i + siz - 1, mx), a, b;
			MinMax(i, r, &a, &b);
			ans = max(ans, a - prv);
			if(b != -1) prv = b;
		}
		ans = max(ans, mx - prv);
		return ans;
	}
}

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