Submission #767984

#	Time	Username	Problem	Language	Result	Execution time	Memory
767984		SanguineChameleon	Shortcut (IOI16_shortcut)	C++17	71 / 100	2061 ms	1924 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;
	}
	for (int i = 1; i <= n; i++) {
		for (int j = i + 1; j <= n; j++) {
			if (sum_lt <= pos[i] + pos[j] && pos[i] + pos[j] <= sum_rt && diff_lt <= pos[j] - pos[i] && pos[j] - pos[i] <= diff_rt) {
				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