Submission #120761

#	Time	Username	Problem	Language	Result	Execution time	Memory
120761		roseanne_pcy	Rail (IOI14_rail)	C++14	8 / 100	79 ms	592 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;
		// printf("tag = %d\n", tag);
		location[tag] = dist0[tag];
		// printf("%d->%d\n", tag, location[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(tag == 11 && x == 8) printf("%d = %d\n", distr[x], xt+dist0[x]-2*location[tag]);
				if(last || distr[x] == xt + dist0[x] - 2*location[tag])
				{
					location[x] = calc;
					stype[x] = 1;
					// printf("det'ed %d->%d\n", x, location[x]);
				}
				else
				{
					bad.pb(x);
				}
			}
			else bad.pb(x);
		}
		tor = bad;
	}
	for(int i = 0; i< N; i++) location[i] += first;
	stype[0] = 1;
	// for(int i = 0; i< N; i++) printf("%d %d\n", stype[i], location[i]);
}

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