제출 #708601

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
708601		ntdxl05	Gap (APIO16_gap)	C++14	70 / 100	63 ms	4364 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);

	long long 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}};
	long long l = x + 1;
	for (int i = 0; i < N - 1; i++) {
		long long 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});
	h[0] = {-1, x};
	h[m - 1] = {y, -1};
	long long res = 0;
	for (int i = 1; i + 1 < m; i++) {
		if (vv[i].first <= vv[i].second) {
			MinMax(vv[i].first, vv[i].second, &x, &y);
			h[i] = {x, y};
		}
	}

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

	return res;
}

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