Submission #60374

#	Time	Username	Problem	Language	Result	Execution time	Memory
60374		kingpig9	Shortcut (IOI16_shortcut)	C++11	71 / 100	610 ms	4736 KiB

shortcut

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

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> edge;
const int MAXN = 3010;	//2*(max N) actually.
const ll INF = 0x3f3f3f3f3f3f3f3f;

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))

template<class T>
void setmin (T &a, T b) {
	if (b < a) {
		a = b;
	}
}

template<class T>
void setmax (T &a, T b) {
	if (a < b) {
		a = b;
	}
}

int N;
ll C;
ll L[MAXN];	//length from (i-1) to i
ll PL[MAXN];
ll D[MAXN];	//distance to secondary station (i + N)

bool moo (ll dia) {
	//is diameter <= dia?
	ll xmymn = LLONG_MIN, xmymx = LLONG_MAX;
	ll xpymn = LLONG_MIN, xpymx = LLONG_MAX;

	for (int i = 0; i < N; i++) {
		for (int j = i + 1; j < N; j++) {
			if (D[i] + (L[j] - L[i]) + D[j] > dia) {
				ll lim = dia - D[i] - D[j] - C;
				if (lim < 0) {
					return false;
				}
				//L[i] - L[j] - lim <= x - y <= L[i] - L[j] + lim
				//L[i] + L[j] - lim <= x + y <= L[i] + L[j] + lim
				setmax(xmymn, L[i] - L[j] - lim);
				setmin(xmymx, L[i] - L[j] + lim);
				setmax(xpymn, L[i] + L[j] - lim);
				setmin(xpymx, L[i] + L[j] + lim);
			}
			//otherwise everything works
		}
	}
	//debug("x - y: min = %lld, max = %lld.\nx + y: min = %lld, max = %lld.\n", xmymn, xmymx, xpymn, xpymx);

	//ok now check if anything is in there
	for (int i = 0; i < N; i++) {
		for (int j = i + 1; j < N; j++) {
			if (xmymn <= L[i] - L[j] && L[i] - L[j] <= xmymx) {
				if (xpymn <= L[i] + L[j] && L[i] + L[j] <= xpymx) {
					return true;
				}
			}
		}
	}
	return false;
}

ll find_shortcut (int nnn, vector<int> lll, vector<int> ddd, int ccc) {
	//very very preliminary stuff - should also init other stuff
	N = nnn;
	C = ccc;
	for (int i = 1; i < N; i++) {
		L[i] = L[i - 1] + lll[i - 1];
	}
	for (int i = 0; i < N; i++) {
		D[i] = ddd[i];
	}

	ll lo = 0, hi = 1ll << 43;
	while (hi - lo > 1) {
		ll mid = (lo + hi) >> 1;
		if (moo(mid)) {
			hi = mid;
		} else {
			lo = mid;
		}
	}
	return hi;
}

• 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