제출 #958996

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
958996		MinaRagy06	Shortcut (IOI16_shortcut)	C++17	97 / 100	2027 ms	100168 KiB

shortcut

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#include "shortcut.h"
#ifdef MINA
#include "grader.cpp"
#endif
using namespace std;
#define ll long long

const ll inf = 1e18;
ll find_shortcut(int n, vector<int> l, vector<int> a, int c) {
	reverse(l.begin(), l.end()), l.push_back(0), reverse(l.begin(), l.end()), l.push_back(0);
	reverse(a.begin(), a.end()), a.push_back(-1), reverse(a.begin(), a.end());
	ll prf[n + 2]{}, vals[n + 2];
	prf[1] = 1;
	for (int i = 2; i <= n; i++) {
		prf[i] = prf[i - 1] + l[i - 1];
	}
	for (int i = 1; i <= n; i++) {
		vals[i] = prf[i];
	}
	sort(vals + 1, vals + n + 1);
	ll s[n + 2]{}, d[n + 2]{};
	for (int i = 1; i <= n; i++) {
		s[i] = prf[i] + a[i];
		d[i] = prf[i] - a[i];
	}
	array<ll, 3> vals2[n + 1];
	for (int i = 1; i <= n; i++) {
		vals2[i] = {prf[i] + a[i], s[i], d[i]};
	}
	sort(vals2 + 1, vals2 + n + 1);
	vector<int> order(n);
	for (int i = 1; i <= n; i++) {
		order[i - 1] = i;
	}
	sort(order.begin(), order.end(), [&] (int x, int y) {return prf[x] - a[x] > prf[y] - a[y];});
	auto check = [&] (ll t) {
		ll l1 = -inf, r1 = inf, l2 = -inf, r2 = inf;
		int ptr = n;
		ll mxs[2] = {-inf, -inf}, mnd[2] = {inf, inf};
		for (auto i : order) {
			while (ptr > 0 && vals2[ptr][0] > t + prf[i] - a[i]) {
				mxs[1] = max(mxs[1], vals2[ptr][1]);
				if (mxs[0] < mxs[1]) swap(mxs[0], mxs[1]);
				mnd[1] = min(mnd[1], vals2[ptr][2]);
				if (mnd[0] > mnd[1]) swap(mnd[0], mnd[1]);
				ptr--;
			}
			ll sj = mxs[0], dj = mnd[0];
			if (prf[i] + a[i] > t + prf[i] - a[i]) {
				if (mxs[0] == s[i]) sj = mxs[1];
				if (mnd[0] == d[i]) dj = mnd[1];
			}
			l1 = max(l1, s[i] + sj - t + c);
			r1 = min(r1, d[i] + dj + t - c);
			l2 = max(l2, - d[i] + sj - t + c);
			r2 = min(r2, - s[i] + dj + t - c);
		}
// 		for (int i = 1; i <= n; i++) {
// 			for (int j = 1; j <= n; j++) {
// 				if (i == j) continue;
// 				if (prf[j] + a[j] > t + prf[i] - a[i]) {
// 					l1 = max(l1, s[i] + s[j] - t + c);
// 					r1 = min(r1, d[i] + d[j] + t - c);
// 					l2 = max(l2, - d[i] + s[j] - t + c);
// 					r2 = min(r2, - s[i] + d[j] + t - c);
// 				}
// 			}
// 		}
		ptr = n;
		ll mn = 1e18;
		int lst = 0;
		for (int x = 1; x <= n; x++) {
			if (prf[x] > (l1 - l2) / 2) {
				break;
			}
			lst = x;
			ll st = l1 - vals[x];
			while (ptr > 0 && st <= vals[ptr]) {
				mn = min(mn, vals[ptr]);
				ptr--;
			}
			ll en = min(r1 - vals[x], r2 + vals[x]);
			if (mn <= en) {
				return true;
			}
		}
		ptr = n, mn = 1e18;
		for (int x = n; x > lst; x--) {
			ll st = l2 + vals[x];
			while (ptr > 0 && st <= vals[ptr]) {
				mn = min(mn, vals[ptr]);
				ptr--;
			}
			ll en = min(r1 - vals[x], r2 + vals[x]);
			if (mn <= en) {
				return true;
			}
		}
		return false;
	};
	ll st = 0, en = 1e18;
	while (st <= en) {
		ll md = (st + en) >> 1;
		if (check(md)) {
			en = md - 1;
		} else {
			st = md + 1;
		}
	}
	return st;
}

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