Submission #107616

#	Time	Username	Problem	Language	Result	Execution time	Memory
107616		Minnakhmetov	Gap (APIO16_gap)	C++14	100 / 100	77 ms	3304 KiB

gap

#include "gap.h"
#include <algorithm>
#include <vector>
using namespace std;

#define ll long long
const ll MAX = 1e18;
const int N = 1e5 + 5;
ll a[N];

long long findGap(int t, int n)
{
	ll ans = 1;

	if (t == 1) {
		ll l = 0, r = MAX;
		int x = 0, y = n - 1;
		while (x <= y) {
			MinMax(l, r, &a[x], &a[y]);
			l = a[x] + 1;
			r = a[y] - 1;
			x++;
			y--;
		}
		for (int i = 0; i < n - 1; i++)
			ans = max(ans, a[i + 1] - a[i]);
	}
	else {
		ll L, R, mn, mx, x;
		MinMax(0, MAX, &L, &R);

		x = (R - L - 1) / (n - 1) + 1;

		vector<pair<ll, ll>> v;
		for (ll i = L; i <= R; i += x + 1) {
			MinMax(i, i + x, &mn, &mx);
			if (mn != -1) {
				v.push_back({ mn, mx });
				ans = max(ans, mx - mn);
			}
		}

		for (int i = 1; i < v.size(); i++) {
			ans = max(ans, v[i].first - v[i - 1].second);
		}
	}

	return ans;
}

Compilation message (stderr)

gap.cpp: In function 'long long int findGap(int, int)':
gap.cpp:43:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 1; i < v.size(); i++) {
                   ~~^~~~~~~~~~

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