Submission #960086

#	Time	Username	Problem	Language	Result	Execution time	Memory
960086		MinaRagy06	Gap (APIO16_gap)	C++17	100 / 100	44 ms	2868 KiB

gap

#include <bits/stdc++.h>
#include "gap.h"
#ifdef MINA
#include "grader.cpp"
#endif
using namespace std;
#define ll long long

const ll inf = 1e18;
ll findGap(int t, int n) {
	if (t == 1) {
		ll s, e;
		MinMax(0, inf, &s, &e);
		int rem = n - 2;
		ll mx = 0;
		while (rem > 0) {
			ll news, newe;
			MinMax(s + 1, e - 1, &news, &newe);
			mx = max(mx, news - s);
			mx = max(mx, e - newe);
			s = news, e = newe;
			rem -= 2;
		}
		mx = max(mx, e - s);
		return mx;
	}
	ll s, e;
	MinMax(0, inf, &s, &e);
	if (n == 2) {
		return e - s;
	}
	ll len = e - s;
	ll b = (len + n - 2) / (n - 1);
	ll lst = s, mx = b;
	ll en = e;
	for (ll i = s + 1; i <= en - 1; i += b) {
		MinMax(i, min(i + b - 1, en - 1), &s, &e);
		if (s == -1) continue;
		mx = max(mx, s - lst);
		lst = e;
	}
	mx = max(mx, en - lst);
	return mx;
}

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