Submission #612826

#	Time	Username	Problem	Language	Result	Execution time	Memory
612826		Temmie	Shortcut (IOI16_shortcut)	C++17	23 / 100	1 ms	304 KiB

shortcut

#include <bits/stdc++.h>

bool check(long long mid, const std::vector <int>& d, const std::vector <long long> her[2], const std::vector <int> ord[2], const std::vector <long long>& pre, int c, int n) {
	long long corners[2][2];
	long long hbb[2], hsbb[2], hwb[2];
	corners[0][0] = corners[0][1] = corners[1][0] = corners[1][1] = hbb[0] = hbb[1] = hsbb[0] = hsbb[1] = -(1LL << 60);
	hwb[0] = hwb[1] = -1;
	for (int i = 0; i < n; i++) {
		int rb = n - 1;
		if (mid - 10 < static_cast <long long> (2e9)) {
			while (~rb && her[0][i] + her[1][rb] > mid) {
				for (int k = 0; k < 2; k++) {
					long long now = d[ord[1][rb]] + (k ? -pre[ord[1][rb]] : pre[ord[1][rb]]);
					if (now > hbb[k]) {
						hsbb[k] = hbb[k];
						hbb[k] = now;
						hwb[k] = ord[1][rb];
					} else if (now > hsbb[k]) {
						hsbb[k] = now;
					}
				}
				rb--;
			}
			for (int ii = 0; ii < 2; ii++) {
				for (int jj = 0; jj < 2; jj++) {
					corners[ii][jj] = std::max(corners[ii][jj], c - mid + d[ord[0][i]] + (hwb[jj] == ord[0][i] ? hsbb[jj] : hbb[jj]) + (ii ? -pre[ord[0][i]] : pre[ord[0][i]]));
				}
			}
		} else {
			while (~rb && her[0][i] + her[1][rb] > mid) {
				for (int k = 0; k < 2; k++) {
					hbb[k] = std::max(hbb[k], (long long) d[ord[1][rb]] + (k ? -pre[ord[1][rb]] : pre[ord[1][rb]]));
				}
				rb--;
			}
			for (int ii = 0; ii < 2; ii++) {
				for (int jj = 0; jj < 2; jj++) {
					corners[ii][jj] = std::max(corners[ii][jj], c - mid + d[ord[0][i]] + hbb[jj] + (ii ? -pre[ord[0][i]] : pre[ord[0][i]]));
				}
			}
		}
		if (corners[0][0] + corners[1][1] > 0LL || corners[0][1] + corners[1][0] > 0LL) {
			return false;
		}
	}
	for (int i = 0; i < n; i++) {
		long long l = std::max(+corners[0][0] - pre[i], +corners[1][0] + pre[i]);
		long long r = std::min(-corners[0][1] + pre[i], -corners[1][1] - pre[i]);
		if (l > r) {
			continue;
		}
		auto lb = std::lower_bound(pre.begin(), pre.end(), l);
		if (lb != pre.end() && *lb <= r) {
			return true;
		}
	}
	return false;
}

long long find_shortcut(int n, std::vector <int> el, std::vector <int> d, int c) {
	if (n == 2) {
		return (long long) std::min(el[0], c) + d[0] + d[1];
	}
	std::vector <long long> pre(n, 0);
	for (int i = 1; i < n; i++) {
		pre[i] = pre[i - 1] + el[i - 1];
	}
	std::vector <long long> her[2];
	her[0].resize(n);
	her[1].resize(n);
	for (int i = 0; i < n; i++) {
		her[0][i] = +pre[i] + d[i];
		her[1][i] = -pre[i] + d[i];
	}
	std::vector <int> ord[2];
	for (int i = 0; i < 2; i++) {
		ord[i].resize(n);
		std::iota(ord[i].begin(), ord[i].end(), 0);
		std::sort(ord[i].begin(), ord[i].end(), [&] (int u, int v) -> bool { return her[i][u] < her[i][v]; });
		std::sort(her[i].begin(), her[i].end());
	}
	long long l = 0, r = 1LL << 55;
	while (l != r) {
		long long mid = (l + r) >> 1;
		if (check(mid, d, her, ord, pre, c, n)) {
			r = mid;
		} else {
			l = mid + 1;
		}
	}
	return l;
}

• Subtask 1: 9 / 9
• Subtask 2: 14 / 14
• Subtask 3: 0 / 8
• Subtask 4: 0 / 7
• Subtask 5: 0 / 33
• Subtask 6: 0 / 22
• Subtask 7: 0 / 4
• Subtask 8: 0 / 3