Submission #1130676

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130676		OI_Account	Gap (APIO16_gap)	C++20	100 / 100	43 ms	4152 KiB

gap

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

typedef long long ll;

const int N = 100'000;
const ll INF = 1'000'000'000'000'000'000;

ll n, t, a[N + 10];

void readInput(int x, int y) {
	t = x;
	n = y;
}

pair<ll, ll> ask(ll s, ll t) {
	ll a, b;
	MinMax(s, t, &a, &b);
	return {a, b};
}

ll calcMax() {
	ll mx = 0;
	for (int i = 1; i < n; i++)
		mx = max(mx, a[i + 1] - a[i]);
	return mx;
}

ll solve1() {
	ll x = 0, y = INF;
	for (int i = 1, j = n; i <= j; i++, j--) {
		pair<ll, ll> p = ask(x, y);
		x = p.first;
		y = p.second;
		a[i] = x;
		a[j] = y;
		x++;
		y--;
		//cout << i << ' ' << j << ": " << x << ' ' << y << endl;
	}
	return calcMax();
}

ll solve2() {
	pair<ll, ll> p = ask(0, INF);
	ll mn = p.first, mx = p.second;
	ll len = mx - mn + 1;
	vector<ll> vec;
	for (int i = 0; i < len % n; i++)
		vec.push_back((len + n - 1) / n);
	while (vec.size() < n)
		vec.push_back(len / n);
	vector<pair<ll, ll>> all;
	ll pnt = mn;
	for (int i = 0; i < vec.size(); i++) {
		pair<ll, ll> tmp;
		if (i == 0) {
			if (vec[i] == 1)
				tmp = {mn, mn};
			else {
				pair<ll, ll> p = ask(pnt + 1, pnt + vec[i] - 1);
				if (p.second == -1)
					tmp = {mn, mn};
				else
					tmp = {mn, p.second};
			}
		}
		else
			tmp = ask(pnt, pnt + vec[i] - 1);
		if (tmp.first != -1)
			all.push_back(tmp);
		pnt += vec[i];
	}
	ll ans = 0;
	for (int i = 1; i < all.size(); i++)
		ans = max(ans, all[i].first - all[i - 1].second);
	return ans;
}

ll solve() {
	if (t == 1)
		return solve1();
	return solve2();
}

long long findGap(int T, int N) {
	readInput(T, N);
	return solve();
}

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