Submission #456446

#	Time	Username	Problem	Language	Result	Execution time	Memory
456446		nonsensenonsense1	Gap (APIO16_gap)	C++17	0 / 100	32 ms	1984 KiB

gap

#include "gap.h"
#include <cassert>
#include <algorithm>

const long long N = 1000000000000000000;

long long task1(int n) 
{
	long long l = 0, r = N, ans = 0;
	for (int i = 0; i * 2 < n; ++i) {
		long long ll, rr;
		MinMax(l, r, &ll, &rr);
		if (l) ans = std::max(ans, ll - l + 1);
		if (r != N) ans = std::max(ans, r - rr + 1);
		if (i * 2 == n - 2) ans = std::max(ans, rr - ll);
		l = ll + 1;
		r = rr - 1;
	}
	return ans;
}

inline long long d(int n, int k, long long l, long long r) 
{
	return l + (__int128)(r - l) * k / n;
}

long long task2(int n) 
{
	long long l, r;
	MinMax(0, N, &l, &r);
	if (n == 2) return r - l;
	++l;
	long long pr = l, ans = 0, len = d(n - 2, 1, l, r) - d(n - 2, 0, l, r);
	for (int i = 0; i < n - 2; ++i) {
		long long ll, rr;
		assert(abs(len - d(n - 2, i + 1, l, r) + d(n - 2, i, l, r)) <= 1);
		MinMax(d(n - 2, i, l, r), d(n - 2, i + 1, l, r) - 1, &ll, &rr);
		if (ll != -1) {
			ans = std::max(ans, ll - pr);
			pr = rr;
		}
	}
	return std::max(ans, r - pr);
}

long long findGap(int t, int n) 
{
	assert(n < 100000);
	if (t == 1) return task1(n);
	return task2(n);
}

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