Submission #545014

#	Time	Username	Problem	Language	Result	Execution time	Memory
545014		Bobby	Shortcut (IOI16_shortcut)	C++17	71 / 100	2070 ms	2176 KiB

shortcut

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
using D = double;
using uint = unsigned int;

#ifdef WIN32
    #define LLD "%I64d"
#else
    #define LLD "%lld"
#endif

#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second

const int maxn = 1000005;
const ll inf = 1e18;

ll x[maxn], d[maxn];
int ans1, ans2;
int n, m;
int C;

inline bool in(ll x, ll lb, ll ub)
{
	return x >= lb && x <= ub;
}

bool can(ll maxd)
{
	ll maxsum = inf;
	ll minsum = -inf;
	ll maxdif = inf;
	ll mindif = -inf;
	for (int i = 0; i < n; i++)
	{
		for (int j = i + 1; j < n; j++)
		{
			if (x[j] - x[i] + d[j] + d[i] > maxd)
			{
				maxsum = min(maxsum, x[i] + x[j] + (maxd - C - d[i] - d[j]));
				minsum = max(minsum, x[i] + x[j] - (maxd - C  - d[i] - d[j]));
				maxdif = min(maxdif, x[j] - x[i] + (maxd - C  - d[i] - d[j]));
				mindif = max(mindif, x[j] - x[i] - (maxd - C  - d[i] - d[j]));
			}
		}
	}
	if (maxsum < minsum || maxdif < mindif) return false;
	for (int i = 0; i < n; i++)
	{
		for (int j = i + 1; j < n; j++) if (in(x[i] + x[j], minsum, maxsum) && in(x[j] - x[i], mindif, maxdif))
		{
			ans1 = i;
			ans2 = j;
			return true;
		}
	}
	return false;
}

long long find_shortcut(int N, vector <int> L0, vector <int> L, int C_)
{
	C = C_;
	n = N;
	ll curlen = 0;
	for (int i = 0; i < n; i++)
	{
		d[i] = L[i];
		x[i] = curlen;
		if (i + 1 < n) curlen += L0[i];
	}
	ll l = 0;
	ll r = inf;
	while (r - l > 1)
	{
		ll mid = (l + r) / 2;
		if (can(mid)) r = mid;
		else l = mid;
	}
// 	cerr << r << ' ' << curlen << endl;
// 	cerr << minres << endl;
// 	for (int i = 0; i < n; i++) cerr << d[i] << ' ';
// 	cerr << endl;
	assert(can(r));
	return r;
	//end1 = ans1;
	//end2 = ans2;
}

• 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