Submission #1012075

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012075		zsombor	Gap (APIO16_gap)	C++17	100 / 100	42 ms	2684 KiB

gap

#include "gap.h"
#include <vector>
using namespace std;
using ll = long long;

const ll m = 1000000000000000000;

ll solve1(ll n) {
	ll l = 0, r = m, mn, mx, ans = 0;
	vector <ll> v;
	vector <ll> v2;
	while (v.size() + v2.size() < n) {
		MinMax(l, r, &mn, &mx);
		l = mn + 1;
		r = mx - 1;
		v.push_back(mn);
		v2.push_back(mx);
	}
	while (v2.size()) { v.push_back(v2.back()); v2.pop_back(); }
	for (int i = 1; i < v.size(); i++) ans = max(ans, v[i] - v[i - 1]);
	return ans;
}

ll solve2(ll n) {
	ll a1, an, mn, mx, ans = 0;
	MinMax(0, m, &a1, &an);
	ll u = a1, d = a1, l = (an - a1) / (n - 1);
	if (l * (n - 1) < an - a1) l++;
	while (d < an) {
		MinMax(d + 1, d + l, &mn, &mx);
		d += l;
		if (mn == -1) continue;
		ans = max(ans, mn - u);
		u = mx;
	}
	return ans;
}

ll findGap(int T, int N) {
	return (T == 1 ? solve1(N) : solve2(N));
}

Compilation message (stderr)

gap.cpp: In function 'll solve1(ll)':
gap.cpp:12:30: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   12 |  while (v.size() + v2.size() < n) {
      |         ~~~~~~~~~~~~~~~~~~~~~^~~
gap.cpp:20:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |  for (int i = 1; i < v.size(); i++) ans = max(ans, v[i] - v[i - 1]);
      |                  ~~^~~~~~~~~~

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