Submission #126776

#	Time	Username	Problem	Language	Result	Execution time	Memory
126776		anayk	Rail (IOI14_rail)	C++14	100 / 100	170 ms	712 KiB

rail

#include <algorithm>
#include <iostream>

#include "rail.h"

#define U 1
#define D 0
#define L 0
#define R 1

void findLocation(int N, int first, int location[], int stype[])
{
	stype[0] = 1;
	location[0] = first;

	std::pair<int, int> d[N-1];

	for(int i = 1; i < N; i++)
	{
		d[i-1].first = getDistance(0, i);
		d[i-1].second = i;
	}

	std::sort(d, d+N-1);

	int hinge = d[0].second;
	int ends[2][2];
	for(int i = 0; i < 2; i++)
		for(int j = 0; j < 2; j++)
			ends[i][j] = -1;

	ends[U][L] = ends[U][R] = d[0].second;
	ends[D][R] = 0;
	location[hinge] = d[0].first + first;
	stype[hinge] = 2;

	for(int i = 1; i < N-1; i++)
	{
		int u = d[i].second;
		int a = getDistance(u, hinge);

		if(a + d[0].first == d[i].first)
		{
			if(ends[D][L] == -1)
			{
				ends[D][L] = u;
				location[u] = location[hinge] - a;
				stype[u] = 1;
				if(location[u] > location[ends[D][R]])
					ends[D][R] = u;
				continue;
			}

			int b = getDistance(u, ends[D][L]);
			int x = location[ends[D][L]] + b;
			int y = -1;

			int j = 0;
			while((location[d[j].second] > x) || (stype[d[j].second] != 1))
			{
				j++;
			}

			y = d[j].second;
			if(d[j].first + x - location[y] != d[i].first)
			{
				location[u] = location[hinge] - a;
				stype[u] = 1;
				ends[D][L] = u;
				if(location[u] > location[ends[D][R]])
					ends[D][R] = u;
			}
			else
			{
				location[u] = location[ends[D][L]] + b;
				stype[u] = 2;
				if(location[u] < location[ends[U][L]])
					ends[U][L] = u;
			}
		}
		else
		{
			int b = getDistance(u, ends[U][R]);
			int x = location[ends[U][R]] - b;

			int j = 0;
			while(stype[d[j].second] != 2 || location[d[j].second] < x)
				j++;

			int y = d[j].second;

			if(d[j].first + location[y] - x != d[i].first)
			{
				location[u] = d[i].first + first;
				stype[u] = 2;
				ends[U][R] = u;
			}
			else
			{
				location[u] = location[ends[U][R]] - b;
				stype[u] = 1;
				if(location[u] > location[ends[D][R]])
					ends[D][R] = u;
			}
		}
	}
}

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