Submission #800250

#	Time	Username	Problem	Language	Result	Execution time	Memory
800250		pavement	Gap (APIO16_gap)	C++17	100 / 100	51 ms	3268 KiB

gap

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

#define pb push_back

using ll = long long;

ll findGap(int T, int N) {
	if (T == 1) {
		ll x, y, l = 0, r = (ll)1e18, ans = 0;
		vector<ll> lh, rh, all;
		while (l <= r && lh.size() + rh.size() < N) {
			MinMax(l, r, &x, &y);
			if (x == -1) break;
			lh.pb(x);
			if (x != y) rh.pb(y);
			l = x + 1;
			r = y - 1;
		}
		reverse(rh.begin(), rh.end());
		for (auto i : lh) all.pb(i);
		for (auto i : rh) all.pb(i);
		for (int i = 1; i < (int)all.size(); i++) {
			ans = max(ans, all[i] - all[i - 1]);
		}
		return ans;
	} else {
		ll x, y;
		MinMax(0, (ll)1e18, &x, &y);
		ll k = (y - x + N - 2) / (N - 1), ans = 0;
		vector<ll> seq;
		seq.pb(x);
		for (ll p = x; p < y; p += k) {
			ll x2, y2;
			MinMax(p + 1, p + k, &x2, &y2);
			if (x2 != -1) {
				seq.pb(x2);
				seq.pb(y2);
			}
		}
		seq.pb(y);
		for (int i = 1; i < (int)seq.size(); i++) {
			ans = max(ans, seq[i] - seq[i - 1]);
		}
		return ans;
	}
}

Compilation message (stderr)

gap.cpp: In function 'll findGap(int, int)':
gap.cpp:13:42: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   13 |   while (l <= r && lh.size() + rh.size() < N) {
      |                    ~~~~~~~~~~~~~~~~~~~~~~^~~

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