Submission #612767

#	Time	Username	Problem	Language	Result	Execution time	Memory
612767		Temmie	Shortcut (IOI16_shortcut)	C++17	71 / 100	2088 ms	2900 KiB

shortcut

#include <bits/stdc++.h>

bool check(long long mid, const std::vector <long long> her[2], const std::vector <long long>& pre, int c, int n) {
	long long ls = -(1LL << 60);
	long long rs = 1LL << 60;
	long long ld = ls;
	long long rd = rs;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (i == j) {
				continue;
			}
			if (her[0][j] - her[1][i] <= mid) {
				continue;
			}
			ls = std::max(ls, her[0][i] + her[0][j] + c - mid);
			rs = std::min(rs, her[1][i] + her[1][j] - c + mid);
			ld = std::max(ld, her[0][i] - her[1][j] + c - mid);
			rd = std::min(rd, her[1][i] - her[0][j] - c + mid);
		}
	}
	if (ls > rs || ld > rd) {
		return false;
	}
	for (int i = 0; i < n - 1; i++) {
		long long l = std::max(ls - pre[i], pre[i] - rd);
		long long r = std::min(rs - pre[i], pre[i] - ld);
		if (l > r) {
			continue;
		}
		int lb = std::lower_bound(pre.begin() + i + 1, pre.end(), l) - pre.begin();
		if (lb != n && pre[lb] <= r) {
			return true;
		}
	}
	return false;
}

long long find_shortcut(int n, std::vector <int> el, std::vector <int> d, int c) {
	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]; });
	}
	long long l = 0, r = 1LL << 55;
	while (l <= r) {
		long long mid = (l + r) >> 1;
		if (check(mid, her, pre, c, n)) {
			r = mid - 1;
		} else {
			l = mid + 1;
		}
	}
	return l;
}

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