Submission #585571

#	Time	Username	Problem	Language	Result	Execution time	Memory
585571		SeDunion	Rail (IOI14_rail)	C++17	30 / 100	79 ms	588 KiB

rail

#include "rail.h"
#include<iostream>

using namespace std;

const int N = 1e6 + 123;

int dist[N];

int n;

const int inf = 1e9;

void findLocation(int N, int first, int location[], int stype[]) {
	n = N;
	location[0] = first;
	stype[0] = 1;
	for (int i = 1 ; i < n ; ++ i) {
		stype[i] = 2;
	}
	int id = -1, mn = inf;
	for (int i = 1 ; i < n ; ++ i) {
		int cur = getDistance(0, i);
		if (mn > cur) {
			mn = cur;
			id = i;
		}
		dist[i] = cur;
		location[i] = cur + first;
	}
	for (int i = 1 ; i < n ; ++ i) {
		if (i == id) continue;
		int cur = getDistance(id, i);
		if (cur < dist[i]) {
			dist[i] = cur;
			stype[i] = 1;
			location[i] = location[id] - cur;
		}
	}
}

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