Submission #708586

#	Time	Username	Problem	Language	Result	Execution time	Memory
708586		ntdxl05	Gap (APIO16_gap)	C++14	0 / 100	35 ms	4412 KiB

gap

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

const long long inf = 1e18;

template<class U, class V>
bool maxz(U &a, V b) {
	if (a < b) return a = b, 1;
	return 0;
}

long long findGap(int T, int N) {
	long long x, y;
	MinMax(0, inf, &x, &y);

	int z = (y - x - 1) / (N - 1), t = (y - x - 1) % (N - 1);
	vector<pair<long long, long long>> vv{pair<long long, long long>{0, x}};
	int l = x + 1;
	for (int i = 0; i < N - 1; i++) {
		int r = l + z + (i < t);
		vv.push_back({l, r - 1});
		// cerr << l << " " << r - 1 << "\n";
		l = r;
	}
	vv.push_back({y, inf});
	int m = vv.size();
	vector<pair<long long, long long>> h(m, {-1, -1});
	for (int i = 1; i + 1 < m; i++) {
		MinMax(vv[i].first, vv[i].second, &x, &y);
		h[i] = {x, y};
	}

	long long res = 0;
	for (int l = 1, r = 1; l + 1 < m; l = r) {
		for (; r + 1 < m && h[r] == h[l]; r++);
		if (h[r].first == -1) {
			long long gap = vv[r].first - vv[l - 1].second;
			maxz(res, gap);
		}
	}

	return res;
}

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