Submission #57968

#	Time	Username	Problem	Language	Result	Execution time	Memory
57968		aome	Rail (IOI14_rail)	C++17	100 / 100	122 ms	1712 KiB

rail

#include "rail.h"

#include <bits/stdc++.h>

using namespace std;

const int N = 5005;

int dis[2][N];

void findLocation(int n, int first, int location[], int stype[]) {
	location[0] = first, stype[0] = 1;
	for (int i = 1; i < n; ++i) {
		dis[0][i] = getDistance(0, i);
	}
	int p1 = 1;
	for (int i = 2; i < n; ++i) {
		if (dis[0][p1] > dis[0][i]) p1 = i;
	}
	location[p1] = location[0] + dis[0][p1], stype[p1] = 2;
	vector<int> vecl, vecr;
	// cout << "#p1 " << p1 << '\n';
	for (int i = 1; i < n; ++i) {
		if (i == p1) continue;
		dis[1][i] = getDistance(p1, i);
		// cout << "#dis1 " << i << ' ' << dis[1][i] << '\n';
		if (dis[0][i] == dis[0][p1] + dis[1][i] && dis[1][i] <= dis[0][p1]) {
			location[i] = location[p1] - dis[1][i], stype[i] = 1;
			// cout << "ax " << i << '\n';
		}
		else {
			if (dis[1][i] + dis[0][p1] == dis[0][i]) vecl.push_back(i);
			else vecr.push_back(i);
		}
	}
	sort(vecl.begin(), vecl.end(), [&] (int x, int y) {
		return dis[1][x] < dis[1][y];
	});
	sort(vecr.begin(), vecr.end(), [&] (int x, int y) {
		return dis[0][x] < dis[0][y];
	});
	// for (auto i : vecl) cout << i << ' '; cout << '\n';
	// for (auto i : vecr) cout << i << ' '; cout << '\n';
	int cur;
	vector<int> vec;
	{	
		cur = p1;
		vec.clear();
		vec.push_back(p1);
		for (auto i : vecr) {
			int tmp1 = getDistance(cur, i);
			int tmp2 = dis[0][i] + location[0];
			int tmp3 = location[cur] - tmp1;
			int p = -1;
			for (auto j : vec) {
				if (location[j] >= tmp3) { p = j; break; }
			}
			// cout << "#at " << i << '\n';
			// cout << cur << ' ' << tmp1 << '\n';
			// cout << tmp2 << ' ' << location[p] << ' ' << tmp3 << '\n';
			if (tmp2 - location[p] == location[p] - tmp3) {
				location[i] = tmp3, stype[i] = 1;
			}
			else {
				location[i] = tmp2, stype[i] = 2, cur = i, vec.push_back(i);
			}
		}
	}
	{
		cur = 0;
		vec.clear();
		vec.push_back(0);
		for (auto i : vecl) {
			int tmp1 = getDistance(cur, i);
			int tmp2 = location[p1] - dis[1][i];
			int tmp3 = location[cur] + tmp1;
			int p = -1;
			for (auto j : vec) {
				if (location[j] <= tmp3) { p = j; break; }
			}
			if (tmp2 - location[p] == location[p] - tmp3) {
				location[i] = tmp3, stype[i] = 2;
			}
			else {
				location[i] = tmp2, stype[i] = 1, cur = i, vec.push_back(i);
			}
		}
	}
	// for (int i = 0; i < n; ++i) {
		// cout << location[i] << ' ' << (stype[i] == 1 ? '(' : ')') << '\n';
	// }
}

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