Submission #367120

#	Time	Username	Problem	Language	Result	Execution time	Memory
367120		dennisstar	Shortcut (IOI16_shortcut)	C++17	97 / 100	2102 ms	45148 KiB

shortcut

#include "shortcut.h"
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const ll INF = 2e15;

int n;
ll c;
vector<int> L, R;
vector<ll> P, D;

bool f(ll m) {
	ll l=-INF, r=INF, d=-INF, u=INF, m1=INF, m2=INF;
	for (int t=0, k=0; t<n; t++) {
		int i=L[t];
		while (k<n) {
			int j=R[k];
			if (P[j]-P[i]+D[i]+D[j]<=m) break;
			ll im=P[j]-D[j];
			if (m1>im) m2=m1, m1=im;
			else if (m2>im) m2=im;
			k++;
		}
		int j=(i==R[0]?R[1]:R[0]);
		if (P[j]-P[i]+D[i]+D[j]<=m) continue;
		ll w=m-c-D[i]-D[j];
		ll x=P[i], y=P[j];
		l=max(l, x+y-w);
		d=max(d, -x+y-w);
		w=m-c-D[i]+(m1==P[i]-D[i]?m2:m1);
		r=min(r, x+w);
		u=min(u, -x+w);
		if (l>r||d>u) return false;
	}
	for (int i=1, j=1; i<=n; i++) {
		ll s=max(l-P[i], d+P[i]);
		ll e=min(r-P[i], u+P[i]);
		if (s>e) continue;
		while (j<=n&&P[j]<s) j++;
		while (j>=1&&P[j-1]>=s) j--;
		if (s<=P[j]&&P[j]<=e) return true;
	}
	return false;
}

ll find_shortcut(int n, vector<int> l, vector<int> d, int c) {
	::n=n;
	::c=c;
	P={-INF, 0};
	for (auto &i:l) P.emplace_back(P.back()+i);
	P.emplace_back(INF);
	D={0};
	for (auto &i:d) D.emplace_back(i);

	for (int i=1; i<=n; i++)
		L.emplace_back(i),
		R.emplace_back(i);
	sort(L.begin(), L.end(), [&](int x, int y) { return P[x]-D[x]>P[y]-D[y]; });
	sort(R.begin(), R.end(), [&](int x, int y) { return P[x]+D[x]>P[y]+D[y]; });
	
	ll s=0, e=INF;
	while (s<e) {
		ll m=(s+e)/2;
		if (f(m)) e=m;
		else s=m+1;
	}

	return s;
}

• 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