Submission #1293479

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293479		kian2009	Gap (APIO16_gap)	C++20	100 / 100	48 ms	3360 KiB

gap

#include <bits/stdc++.h>
#include "gap.h"
using namespace std;

typedef long long ll;

const int MAXN = 1e5 + 10;
const ll N = 1e18;

ll a[MAXN];
vector<ll> num;

ll solve(int n) {
	ll l = 0, r = N, mi, ma;
	for (int i = 0; i < (n + 1) / 2; i++) {
		MinMax(l, r, &mi, &ma);
		a[i] = mi;
		a[n - 1 - i] = ma;
		l = mi + 1;
		r = ma - 1;
	}
	ll res = 0;
	for (int i = 1; i < n; i++)
		res = max(res, a[i] - a[i - 1]);
	return res;
}

ll findGap(int t, int n) {
	if (t == 1)
		return solve(n);
	ll res = 0, b, e, mi, ma;
	MinMax(0, N, &b, &e);
	num.push_back(b);
	if (e - b - 1 < n) {
		for (int i = b + 1; i < e; i++) {
			MinMax(i, i, &mi, &ma);
			if (mi != -1)
				num.push_back(i);	
		}
		num.push_back(e);
		for (int i = 1; i < n; i++)
			res = max(res, num[i] - num[i - 1]);
		return res;
	}
	ll cnt = b + 1, x = (e - b - 1) / n, y = (e - b - 1) % n;
	for (int i = 0; i < n; i++) {
		ll r = cnt + (i < y? x + 1: x);
		MinMax(cnt, r - 1, &mi, &ma);
		if (mi != -1) {
			num.push_back(mi);
			num.push_back(ma);	
		}
		cnt = r;
	}
	num.push_back(e);
	for (int i = 1; i < num.size(); i++)
		res = max(res, num[i] - num[i - 1]);
	return res;
}

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