Submission #704608

#	Time	Username	Problem	Language	Result	Execution time	Memory
704608		SamNguyen	Rail (IOI14_rail)	C++14	30 / 100	81 ms	496 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>

const int TYPE_C = 1, TYPE_D = 2;
const int INF = 1e8;

template <class T1, class T2>
inline bool minimise(T1 &x, T2 y) {
	if (x > y) { x = y; return true; }
	return false;
}

void findLocation(int N, int x0, int x[], int t[]) {
	x[0] = x0;
	t[0] = TYPE_C;

	int p = 0, min_dist_0 = INF;
	for (int i = 1; i < N; i++) 
		if (minimise(min_dist_0, getDistance(0, i)))
			p = i;

	x[p] = x[0] + min_dist_0;
	t[p] = TYPE_D;

	for (int i = 1; i < N; i++) if (i != p) {
		int d1 = getDistance(0, i), d2 = getDistance(p, i);
		if (d1 < d2) {
			x[i] = x[0] + d1;
			t[i] = TYPE_D;
		}
		else {
			x[i] = x[p] - d2;
			t[i] = TYPE_C;
		}
	}
}

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