Submission #585651

#	Time	Username	Problem	Language	Result	Execution time	Memory
585651		SeDunion	Rail (IOI14_rail)	C++17	30 / 100	73 ms	572 KiB

rail

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

using namespace std;

const int N = 5055;
const int inf = 1e9;

int da[N], db[N];

int a = -1, b = -1;

int ask(int x, int y) {
	if (x == y) return 0;
	if (x == a) return da[y];
	if (x == b) return db[y];
	return getDistance(x, y);
}

int n;

void findLocation(int N, int first, int location[], int stype[]) {
	n = N;
	a = 0;
	stype[0] = 1, location[0] = first;
	for (int i = 0 ; i < n ; ++ i) {
		if (i == a) continue;
		da[i] = getDistance(a, i);
	}
	int mn = inf;
	for (int i = 0 ; i < n ; ++ i) {
		if (i == a) continue;
		if (mn > da[i]) {
			mn = da[i];
			b = i;
		}
	}
	for (int i = 0 ; i < n ; ++ i) {
		if (i == a || i == b) continue;
		db[i] = getDistance(b, i);
	}
	stype[b] = 2, location[b] = location[a] + da[b];
	vector<int>left, right;
	for (int i = 0 ; i < n ; ++ i) {
		if (i == a || i == b) {
			continue;
		} 
		if (da[i] < db[i]) {
			right.emplace_back(i);
		} else {
			left.emplace_back(i);
		}
	}
	for (int i : left) {
		location[i] = location[b] - db[i];
		if (getDistance(i, b) == db[i]) {
			stype[i] = 1;
		} else {
			stype[i] = 2;
		}
	}
	for (int i : right) {
		location[i] = location[a] + da[i];
		if (getDistance(i, a) == da[i]) {
			stype[i] = 2;
		} else {
			stype[i] = 1;
		}
	}
}

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