Submission #374060

#	Time	Username	Problem	Language	Result	Execution time	Memory
374060		KoD	Gap (APIO16_gap)	C++17	100 / 100	66 ms	3296 KiB

gap

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

long long findGap(int T, int N) {
	std::vector<long long> vec;
	long long l, r;
	MinMax(0, 1000000000000000000, &l, &r);
	if (T == 1) {
		while (true) {
			vec.push_back(l);
			vec.push_back(r);
			l += 1;
			r -= 1;
			if (l > r || (int) vec.size() >= N) {
				break;
			}
			MinMax(l, r, &l, &r);
			if (l == -1) {
				break;
			}
		}
	}
	else {
		const auto dif = r - l + 1;
		const auto len = (dif + (N - 1) - 1) / (N - 1);
		for (int i = 0; i < N - 1; ++i) {
			long long mn, mx;
			MinMax(l + len * i, l + len * (i + 1) - 1, &mn, &mx);
			if (mn != -1) {
				vec.push_back(mn);
				vec.push_back(mx);
			}
		}
	}
	std::sort(vec.begin(), vec.end());
	long long ans = 0;
	for (int i = 1; i < (int) vec.size(); ++i) {
		ans = std::max(ans, vec[i] - vec[i - 1]);
	}
	return ans;
}

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