Submission #59036

#	Time	Username	Problem	Language	Result	Execution time	Memory
59036		Crown	Shortcut (IOI16_shortcut)	C++14	71 / 100	2027 ms	199300 KiB

shortcut

#include "shortcut.h"

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;

//transform (x, y) into (x+y, -x+y) with sizeof square = 2*d

int n;
vector<int> l, d;
int c;
vector< ll > X;

struct square
{
	ll x, y, d;
	//bottom left coordinates and size
	square(ll _x, ll _y, ll _d)
	{
		x = _x; y = _y; d = _d;
	}
};

vector<square> all;

bool works()
{
	bool bad = false;
	for(auto sq : all)
	{
		if(sq.d< 0) bad = true;
	}
	if(bad) return false;
	if(all.empty()) return true;
	ll xmin = -1e18, ymin = -1e18, xmax = 1e18, ymax = 1e18;
	for(auto sq : all)
	{
		ll sqx = sq.x, sqy = sq.y, sqd = sq.d;
		xmin = max(xmin, sqx);
		xmax = min(xmax, sqx+sqd);
		ymin = max(ymin, sqy);
		ymax = min(ymax, sqy+sqd);
	}
	//printf("survival");
	for(int a = 0; a< n; a++)
	{
		for(int b = a+1; b< n; b++)
		{
			ll _x = X[a], _y = X[b];
			ll bx = _x+_y, by = -_x+_y;
			if(xmin<= bx && bx<= xmax && ymin<= by && by<= ymax) return true;
		}
	}
	return false;
}

ll find_shortcut(int _n, vector<int> _l, vector<int> _d, int _c)
{
	n = _n; l = _l; d = _d; c = _c;
	X.resize(n); X[0] = 0;
	for(int i = 1; i< n; i++)
	{
		X[i] = X[i-1] + l[i-1];
	}
	ll lo = 0, hi = 1e15;
	while(lo< hi)
	{
		ll mid = (lo+hi)/2;
		all.clear();
		//printf("test %lld ", mid);
		for(int a = 0; a< n; a++)
		{
			for(int b = a+1; b< n; b++)
			{
				if(X[b]-X[a]+d[a]+d[b]<= mid) continue;
				ll _x = X[a], _y = X[b];
				ll bx = _x, by = _y-(mid-d[a]-d[b]-c);
				all.pb(square(bx+by, -bx+by, 2LL*(mid-d[a]-d[b]-c)));
			}
		}
		if(works())
		{
			//printf("works");
			hi = mid;
		}
		else lo = mid+1;
		//printf("\n");
	}
	return lo;
}

• 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