Submission #763173

#	Time	Username	Problem	Language	Result	Execution time	Memory
763173		SanguineChameleon	Rail (IOI14_rail)	C++17	30 / 100	45 ms	520 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>
using namespace std;

const int maxN = 5e3 + 20;
int distX[maxN];
int distY[maxN];
int distZ[maxN];

void findLocation(int N, int first, int location[], int stype[]) {
	for (int i = 0; i < N; i++) {
		location[i] = -1;
		stype[i] = -1;
	}
	int X = 0;
	location[X] = first;
	stype[X] = 1;
	for (int i = 0; i < N; i++) {
		if (i != X) {
			distX[i] = getDistance(X, i);
		}
	}
	int Y = 1;
	for (int i = 0; i < N; i++) {
		if (i != X && distX[i] < distX[Y]) {
			Y = i;
		}
	}
	location[Y] = location[X] + distX[Y];
	stype[Y] = 2;
	for (int i = 0; i < N; i++) {
		if (i != Y) {
			distY[i] = getDistance(Y, i);
		}
	}
	for (int i = 0; i < N; i++) {
		if (i == X || i == Y) {
			continue;
		}
		if (distX[i] == distX[Y] + distY[i]) {
			location[i] = location[Y] - distY[i]; 
			stype[i] = 1;
		}
		if (distY[i] == distY[X] + distX[i]) {
			location[i] = location[X] + distX[i]; 
			stype[i] = 2;
		}
	}
}

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