Submission #169785

#	Time	Username	Problem	Language	Result	Execution time	Memory
169785		ZwariowanyMarcin	Gap (APIO16_gap)	C++14	70 / 100	74 ms	4244 KiB

gap

#include "gap.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define ss(x) (int) x.size()
#define pb push_back
#define ll long long
#define cat(x) cerr << #x << " = " << x << endl
#define FOR(i, n) for(int i = 0; i < n; ++i)

using namespace std;	

ll findGap(int t, int n) {
	if(t == 1) {
		vector <ll> v;
		ll L = 0;
		ll R = 1e18;
		while(L <= R) {
			ll LL, RR;
			MinMax(L, R, &LL, &RR);
			if(LL == -1) break;
			v.pb(LL);
			if(LL != RR)
				v.pb(RR);
			L = LL + 1;
			R = RR - 1;
		}
		sort(v.begin(), v.end());
		ll ans = 0;
		for(int i = 0; i + 1 < ss(v); ++i)
			ans = max(ans, v[i + 1] - v[i]);
		return ans;
	}
	// t = 2
	ll L = 0;
	ll R = 1e18;
	ll LL, RR;
	MinMax(L, R, &LL, &RR);
	ll ans = (RR - LL + n - 2) / (n - 1);
	ll Last = -1;
	L = LL;
	R = RR;
	ll P = ans;
	while(L <= R) {
		MinMax(L, L + P, &LL, &RR);
		if(LL == -1) {
			L += P + 1;
			continue;
		}
		if(Last != -1) {
			ans = max(ans, LL - Last);
		}
		Last = RR;
		L += P + 1;
	}
	return ans;
}

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