Submission #246591

#	Time	Username	Problem	Language	Result	Execution time	Memory
246591		faremy	Rail (IOI14_rail)	C++14	100 / 100	115 ms	632 KiB

rail

#include "rail.h"
#include <algorithm>
#include <vector>


const int MAXN = 5e3;

int dist0[MAXN];
int distA[MAXN];
std::vector<int> left, right;

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

	for (int iSta = 1; iSta < N; iSta++)
		dist0[iSta] = getDistance(0, iSta);
	int stationA = std::min_element(dist0 + 1, dist0 + N) - dist0;
	location[stationA] = location[0] + dist0[stationA];
	stype[stationA] = 2;

	distA[0] = dist0[stationA];
	for (int iSta = 1; iSta < N; iSta++)
		if (iSta != stationA)
		{
			distA[iSta] = getDistance(stationA, iSta);
			if (dist0[iSta] == dist0[stationA] + distA[iSta])
				left.emplace_back(iSta);
			else
				right.emplace_back(iSta);
		}

	std::sort(right.begin(), right.end(), [](int a, int b) { return (dist0[a] < dist0[b]); });
	int lastD = -1;

	for (int iSta = 0; iSta < (int)right.size(); iSta++)
	{
		int station = right[iSta];
		location[station] = location[0] + dist0[station];
		stype[station] = 2;

		if (lastD != -1)
		{
			int distLast = getDistance(lastD, station);
			for (int jSta = 0; jSta < iSta; jSta++)
			{
				int stat2 = right[jSta];
				if (stype[stat2] == 2 && distLast - (location[lastD] - location[stat2]) == dist0[station] - (location[stat2] - location[0]))
				{
					location[station] = location[stat2] - dist0[station] + (location[stat2] - location[0]);
					stype[station] = 1;
					break;
				}
			}
		}

		if (stype[station] == 2)
			lastD = station;
	}

	std::sort(left.begin(), left.end(), [](int a, int b) { return (distA[a] < distA[b]); });
	int lastC = -1;

	for (int iSta = 0; iSta < (int)left.size(); iSta++)
	{
		int station = left[iSta];
		location[station] = location[stationA] - distA[station];
		stype[station] = 1;

		if (lastC != -1)
		{
			int distLast = getDistance(lastC, station);
			for (int jSta = 0; jSta < iSta; jSta++)
			{
				int stat2 = left[jSta];
				if (stype[stat2] == 1 && distLast - (location[stat2] - location[lastC]) == distA[station] - (location[stationA] - location[stat2]))
				{
					location[station] = location[stat2] + distA[station] - (location[stationA] - location[stat2]);
					stype[station] = 2;
					break;
				}
			}
		}

		if (stype[station] == 1)
			lastC = station;
	}
}

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