Submission #708580

#	Time	Username	Problem	Language	Result	Execution time	Memory
708580		ntdxl05	Gap (APIO16_gap)	C++14	0 / 100	34 ms	4408 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});
		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 = 0;
			for (int i = l; i < r; i++) gap += vv[i].second - vv[i].first + 1; 
			gap += vv[l].first - vv[l - 1].second;
			gap += vv[r].first - vv[r - 1].first;
			maxz(res, gap);
		}
	}

	return res;
}

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