Submission #547005

#	Time	Username	Problem	Language	Result	Execution time	Memory
547005		blue	Rail (IOI14_rail)	C++17	30 / 100	73 ms	608 KiB

rail

#include "rail.h"
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

using vi = vector<int>;

const int mx = 5'000;

int X;
vi dist0(mx);
vi distX(mx);

const int typeC = 1;
const int typeD = 2;

void findLocation(int N, int first, int location[], int stype[])
{
	dist0[0] = 0;
	for(int i = 1; i < N; i++)
	{
		dist0[i] = getDistance(0, i);
	}

	int lst[N];
	for(int i = 0; i < N; i++)
		lst[i] = i;

	sort(lst, lst+N, [] (int u, int v)
	{
		return dist0[u] < dist0[v];
	});

	X = lst[1];

	location[0] = first;
	stype[0] = typeC;

	location[X] = first + dist0[X];
	stype[X] = typeD;

	int L = 0;
	int R = X;


	for(int i = 0; i < N; i++)
	{
		if(i == 0) distX[0] = dist0[X];
		else if(i == X) distX[X] = 0;
		else distX[i] = getDistance(X, i);
	}

	set<int> Cs;
	set<int> Ds;

	Cs.insert(location[0]);
	Ds.insert(location[X]);

	for(int v = 2; v < N; v++)
	{
		int Q = lst[v];

		if(dist0[X] + distX[Q] != dist0[Q])
		{
			int d = dist0[R] + getDistance(R, Q) - dist0[Q];

			if(Cs.find(location[R] - d/2) != Cs.end())
			{
				location[Q] = first + dist0[Q];
				stype[Q] = typeD;
				R = Q;
			}
			else
			{
				location[Q] = (location[R] - d/2) - (dist0[Q] - (location[R] - d/2 - first));
				stype[Q] = typeC;
			}
		}
		else if(distX[0] + dist0[Q] != distX[Q])
		{
			int d = distX[L] + getDistance(L, Q) - distX[Q];

			if(Ds.find(location[L] + d/2) != Ds.end())
			{
				location[Q] = location[X] - distX[Q];
				stype[Q] = typeC;
				L = Q;
			}
			else
			{
				location[Q] = (location[L] + d/2) + (distX[Q] - (location[X] - (location[L] + d/2)));
				stype[Q] = typeD;
			}
		}
		else
		{
			location[Q] = location[X] - distX[Q];
			stype[Q] = typeC;
		}

		if(stype[Q] == typeC) 
			Cs.insert(location[Q]);
		else
			Ds.insert(location[Q]);
	}
}

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