Submission #768014

#	Time	Username	Problem	Language	Result	Execution time	Memory
768014		SanguineChameleon	Shortcut (IOI16_shortcut)	C++17	71 / 100	2062 ms	1980 KiB

shortcut

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

const int maxn = 1e6 + 20;
const long long inf = 1e15L + 20;
long long pos[maxn];
int depth[maxn];
int n, c;

bool check(long long lim) {
	long long sum_lt = -inf;
	long long sum_rt = inf;
	long long diff_lt = -inf;
	long long diff_rt = inf;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (j != i && pos[j] - pos[i] + depth[i] + depth[j] > lim) {
				sum_lt = max(sum_lt, (pos[j] + depth[j]) + (pos[i] + depth[i]) - (lim - c));
				sum_rt = min(sum_rt, (pos[j] - depth[j]) + (pos[i] - depth[i]) + (lim - c));
				diff_lt = max(diff_lt, (-pos[j] + depth[j] + (pos[i] + depth[i]) - (lim - c)));
				diff_rt = min(diff_rt, (-pos[j] - depth[j]) + (pos[i] - depth[i]) + (lim - c));
			}
		}
	}
	swap(diff_lt, diff_rt);
	diff_lt = -diff_lt;
	diff_rt = -diff_rt;
	if (sum_lt > sum_rt || diff_lt > diff_rt) {
		return false;
	}
	int lt1 = n;
	int lt2 = 1;
	for (int i = 1; i <= n; i++) {
		while (lt1 > 1 && pos[i] + pos[lt1 - 1] >= sum_lt) {
			lt1--;
		}
		while (lt2 <= n && pos[lt2] < pos[i] - diff_rt) {
			lt2++;
		}
		int lt = max(lt1, lt2);
		if (lt < i && pos[lt] <= sum_rt - pos[i] && pos[lt] <= pos[i] - diff_lt) {
			return true;
		}
	}
	return false;
}

long long find_shortcut(int _n, vector<int> len, vector<int> _depth, int _c) {
	n = _n;
	c = _c;
	pos[1] = 0;
	for (int i = 2; i <= n; i++) {
		pos[i] = pos[i - 1] + len[i - 2];
	}
	for (int i = 1; i <= n; i++) {
		depth[i] = _depth[i - 1];
	}
	long long lt = 0;
	long long rt = inf;
	long long res = -1;
	while (lt <= rt) {
		long long mt = (lt + rt) / 2;
		if (check(mt)) {
			res = mt;
			rt = mt - 1;
		}
		else {
			lt = mt + 1;
		}
	}
	return res;
}

• 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