Submission #547011

#	Time	Username	Problem	Language	Result	Execution time	Memory
547011		blue	Rail (IOI14_rail)	C++17	100 / 100	71 ms	844 KiB

rail

#include "rail.h"
#include <vector>
#include <set>
#include <algorithm>
#include <iostream>
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]);

	// cerr << location[0] << ' ' << location[X] << '\n';

	for(int v = 2; v < N; v++)
	{
		int Q = lst[v];
		// cerr << "computing : " << Q << '\n';

		if(dist0[Q] != dist0[X] + distX[Q])
		{
			// cerr << "case 1\n";
			int drq = getDistance(R, Q);

			int d = dist0[R] + drq - dist0[Q];

			// cerr << "drq = " << drq << '\n';

			if(Ds.find(location[R] - d/2) != Ds.end())
			{
				location[Q] = location[R] - drq;
				stype[Q] = typeC;
			}
			else
			{
				location[Q] = location[0] + dist0[Q];
				stype[Q] = typeD;
			}
		}
		else if(distX[Q] != distX[0] + dist0[Q])
		{
			// cerr << "case 2\n";
			int dlq = getDistance(L, Q);

			int d = distX[L] + dlq - distX[Q];

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

		if(location[Q] < location[L])
			L = Q;
		if(location[Q] > location[R])
			R = Q;

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

	// cerr << "computed\n";
	// for(int i = 0; i < N; i++) cerr << stype[i] << ' ' << location[i] << '\n';
}

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