Submission #120775

#	Time	Username	Problem	Language	Result	Execution time	Memory
120775		roseanne_pcy	Rail (IOI14_rail)	C++14	30 / 100	113 ms	636 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;

int n;
const int maxn = 5005;
int dist0[maxn];
int distu[maxn];
int distr[maxn];
int distl[maxn];

void findLocation(int N, int first, int location[], int stype[])
{
	n = N;
	ii near = {1e9, 0};
	for(int i = 1; i< n; i++) 
	{
		dist0[i] = getDistance(0, i);
		near = min(near, {dist0[i], i});
	}
	int u = near.Y;
	vector<int> tol, tor;
	tor.pb(u);
	for(int i = 1; i< n; i++)
	{
		if(i == u) continue;
		distu[i] = getDistance(u, i);
		if(distu[i]> dist0[i]) tor.pb(i);
		else tol.pb(i);
	}
	ii far = {0, 0};
	for(int x : tor)
	{
		far = max(far, {dist0[x], x});
	}
	int T = far.Y, xt = far.X;
	for(int x : tor)
	{
		if(x == u)
		{
			distr[u] = distu[T];
		}
		else distr[x] = getDistance(T, x);
	}
	distr[0] = dist0[T];
	int buff = 0;
	while(!tor.empty())
	{
		ii close = {1e9, 0};
		vector<int> bad;
		for(int x : tor)
		{
			close = min(close, {dist0[x], x});
		}
		int tag = close.Y;
		location[tag] = dist0[tag];
		stype[tag] = 2;
		bool last = false;
		if(distr[tag] == xt-location[tag])
		{
			T = tag;
			xt = location[tag];
			last = true;
		}
		for(int x : tor)
		{
			if(x == tag) continue;
			int calc = dist0[x]-location[tag];
			calc = location[tag]-calc;
			if(buff< calc && calc< location[tag])
			{
				if(last || distr[x] == xt + dist0[x] - 2*location[tag])
				{
					location[x] = calc;
					stype[x] = 1;
				}
				else
				{
					bad.pb(x);
				}
			}
			else bad.pb(x);
		}
		tor = bad;
	}
	far = {0, 0};
	for(int x : tol)
	{
		far = max(far, {dist0[x], x});
	}
	T = far.Y, xt = -(far.X-2*dist0[u]);
	for(int x : tol)
	{
		distr[x] = getDistance(T, x);
	}
	distl[0] = dist0[T];
	while(!tol.empty())
	{
		ii close = {1e9, 0};
		vector<int> bad;
		for(int x : tol)
		{
			close = min(close, {dist0[x], x});
		}
		int tag = close.Y;
		// printf("tag = %d\n", tag);		
		location[tag] = -(dist0[tag]-2*dist0[u]);
		stype[tag] = 1;
		bool last = false;
		if(distl[tag] == location[tag]-xt)
		{
			T = tag;
			xt = location[tag];
			last = true;
		}
		for(int x : tol)
		{
			if(x == tag) continue;
			int calc = (dist0[x]-2*dist0[u]);
			int rem = calc+location[tag];
			calc = location[tag]+rem;
			// printf("calc = %d\n", calc);
			if(location[tag]< calc && calc< buff)
			{
				// printf("%d == %d-%d-%d\n", distl[x], 2*location[u], dist0[x], xt);
				if(last || distl[x] == dist0[x]-2*location[u]+2*location[tag])
				{
					location[x] = calc;
					// printf("det %d->%d\n", x, location[x]);
					stype[x] = 2;
				}
				else
				{
					bad.pb(x);
				}
			}
			else bad.pb(x);
		}
		tol = bad;
	}
	for(int i = 0; i< N; i++) location[i] += first;
	stype[0] = 1;
}

• Subtask 1: 8 / 8
• Subtask 2: 22 / 22
• Subtask 3: 0 / 26
• Subtask 4: 0 / 44