Submission #556054

#	Time	Username	Problem	Language	Result	Execution time	Memory
556054		hollwo_pelw	Gap (APIO16_gap)	C++17	30 / 100	45 ms	1092 KiB

gap

#include <bits/stdc++.h>
#include "gap.h"

using namespace std;

long long solve(int N) {
	long long l, r, res = 0;
	MinMax(0, 1e18, &l, &r);

	for (int i = 1; i <= (N - 1) / 2; i++) {
		long long nl, nr;
		MinMax(l + 1, r - 1, &nl, &nr);

		res = max(res, nl - l), l = nl;
		res = max(res, r - nr), r = nr;
	}

	return max(res, r - l);
}

long long findGap(int T, int N) {
	if (T == 1)
		return solve(N);

	long long l, r;
	MinMax(0, 1e18, &l, &r);

	long long res = (r - l - 1) / (N - 1) + 1;

	cout << res << endl;

	for (long long nl, nr; l < r; l = nr) {
		MinMax(l + 1, l + res, &nl, &nr);
		if (nr != -1) continue ;
	
		MinMax(l + 1, l + (res + 1) * 2, &nl, &nr);
		while (nl == -1) {
			res = (res + 1) * 2 + 1;
			MinMax(l + 1, l + (res + 1) * 2, &nl, &nr);
		}
		res = nl - l;
	}

	return res;
}

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