Submission #136605

#	Time	Username	Problem	Language	Result	Execution time	Memory
136605		mosesmayer	Rail (IOI14_rail)	C++17	30 / 100	84 ms	632 KiB

rail

#include "rail.h"
#include <cstdio>
 
//getDistance(i,j) --> distance from i to j
int d[3][5005];
int type[5005];
int pos[5005];
void findLocation(int n, int first, int location[], int stype[]){
	int mnid = 0;
	d[0][0] = 0x3f3f3f3f;
	for (int i = 1; i < n; i++){
		d[0][i] = getDistance(0, i);
		if (d[0][i] < d[0][mnid]) mnid = i;
	}
	type[mnid] = 2;
	int mnid2 = 0;
	for (int i = 0; i < n; i++){
		if (i == mnid) continue;
		d[1][i] = getDistance(mnid, i);
		if (d[1][i] < d[1][mnid2]) mnid2 = i;
	}
	for (int i = 0; i < n; i++){
		if (i == mnid2) continue;
		d[2][i] = getDistance(mnid2, i);
	}
	pos[mnid] = d[0][mnid] + first;
	pos[mnid2] = pos[mnid] - d[1][mnid2];
	type[mnid] = 2;
	type[mnid2] = 1;
//	printf("%d %d t%d\n", mnid, pos[mnid], type[mnid]);
//	printf("%d %d t%d\n", mnid2, pos[mnid2], type[mnid2]);
	for (int i = 0; i < n; i++){
		if (i == mnid || i == mnid2) continue;
		if (d[1][i] < d[2][i]){
			type[i] = 1;
			pos[i] = pos[mnid] - d[1][i];
		} else {
			type[i] = 2;
			pos[i] = pos[mnid2] + d[2][i];
		}
	}
	for (int i = 0; i < n; i++){
		location[i] = pos[i];
		stype[i] = type[i];
	}
}

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