Submission #38842

#	Time	Username	Problem	Language	Result	Execution time	Memory
38842		14kg	Rail (IOI14_rail)	C++11	30 / 100	106 ms	696 KiB

rail

#include "rail.h"
#include <stdio.h>
#define N 5000
#define INF 999999999

int n;
int zd[N], zero;
int ld[N], lw, l_num;
int rd[N], rw, r_num;

void findLocation(int _n, int _zero, int out1[], int out2[]) {
	int temp = INF;
	n = _n, zero = _zero;

	for (int i = 1; i < n; i++) {
		zd[i] = getDistance(0, i);
		if (temp > zd[i]) {
			temp = zd[i], r_num = i;
			rw = zero + temp;
		}
	}

	temp = INF;
	for (int i = 0; i < n; i++)
	if (i != r_num) {
		rd[i] = getDistance(r_num, i);
		if (temp > rd[i]) {
			temp = rd[i], l_num = i;
			lw = rw - temp;
		}
	}
	for (int i = 1; i < n; i++)
		if (i != l_num && i != r_num) ld[i] = getDistance(l_num, i);

	out1[0] = zero, out2[0] = 1;
	out1[r_num] = rw, out2[r_num] = 2;
	out1[l_num] = lw, out2[l_num] = 1;

	for (int i = 1; i <= n; i++)
		if (i != l_num && i != r_num) {
			//printf("%d %d / %d %d\n", ld[i], rd[i], lw, rw);
			if (ld[i] + rw - lw == rd[i])
				out1[i] = lw + ld[i], out2[i] = 2;
			else if (rd[i] + rw - lw == ld[i])
				out1[i] = rw - rd[i], out2[i] = 1;
		}
}

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