Submission #409430

#	Time	Username	Problem	Language	Result	Execution time	Memory
409430		robs	Rail (IOI14_rail)	C++17	30 / 100	94 ms	448 KiB

rail

#include "rail.h"
#define debug(args...) fprintf(stderr, args)
const int maxn = 5e5, INF = 1e9;
int d[maxn], r[maxn], mn, id;

void findLocation(int N, int first, int location[], int stype[])
{
	mn = INF;
	for(int x = 1; x < N; x++)
		d[x] = getDistance(0, x);
	for(int x = 1; x < N; x++)
		if(d[x] < mn)
		{
			mn = d[x];
			id = x;
		}
	location[0] = first;
	stype[0] = 1;
	location[id] = first+d[id];
	stype[id] = 2;
	for(int x = 1; x < N; x++)
		r[x] = getDistance(id, x);
	for(int x = 1; x < N; x++)
	{
		if(x == id)	continue;
		if(d[x] < r[x])
		{
			location[x] = first+d[x];
			stype[x] = 2;
		}
		else
		{
			location[x] = location[id]-r[x];
			stype[x] = 1;
		}
	}
}

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