제출 #795070

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
795070		pavement	철로 (IOI14_rail)	C++17	30 / 100	137 ms	896 KiB

rail

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

#define pb push_back

void findLocation(int N, int first, int location[], int stype[]) {
	vector<int> dist0(N), dista(N), distl(N), distr(N);
	stype[0] = 1;
	location[0] = first;
	if (N == 1) {
		return;
	}
	vector<int> left, right;
	int a = -1;
	for (int x = 1; x < N; x++) {
		dist0[x] = getDistance(0, x);
		if (a == -1 || dist0[x] < dist0[a]) {
			a = x;
		}
	}
	int b = dist0[a] + first, c = -1;
	stype[a] = 2;
	location[a] = b;
	for (int x = 0; x < N; x++) {
		if (x == a) {
			continue;
		}
		dista[x] = getDistance(a, x);
		if (c == -1 || dista[x] < dista[c]) {
			c = x;
		}
	}
	int d = b - dista[c];
	stype[c] = 1;
	location[c] = d;
	for (int x = 0; x < N; x++) {
		if (x == 0 || x == a) {
			continue;
		}
		if (dista[x] < dist0[a]) {
			stype[x] = 1;
			location[x] = dista[x] + b;
		} else if (dista[x] < dist0[x]) {
			// left
			left.pb(x);
		} else {
			// right
			right.pb(x);
		}
	}
	sort(left.begin(), left.end(), [dista](const auto &lhs, const auto &rhs) {
		return dista[lhs] < dista[rhs];
	});
	sort(right.begin(), right.end(), [dista](const auto &lhs, const auto &rhs) {
		return dista[lhs] < dista[rhs];
	});
	if (!left.empty()) {
		// handle left side
		int closestUp = a;
		for (int i = 1; i < (int)left.size(); i++) {
			distl[left[i]] = getDistance(left[0], left[i]);
		}
		stype[left[0]] = 1;
		location[left[0]] = b - dista[left[0]];		
		while (1) {
			for (int i = 0; i < (int)left.size(); i++) {
				distl[left[i]] = getDistance(left[0], left[i]);
			}
			vector<int> to_erase;
			for (int i = 1; i < (int)left.size(); i++) {
				if (dista[left[i]] == dista[left[0]] + distl[left[i]]) {
					// to the right of left[0]
					stype[left[i]] = 2;
					location[left[i]] = distl[left[i]] + location[left[0]];
					if (location[closestUp] > location[left[i]]) {
						closestUp = left[i];
					}
					to_erase.pb(i);
				}
			}
			vector<int> new_left;
			for (int i = 1; i < (int)left.size(); i++) {
				if (!binary_search(to_erase.begin(), to_erase.end(), i)) {
					new_left.pb(left[i]);
				}
			}
			if (new_left.empty()) {
				break;
			}
			stype[new_left[0]] = 1;
			location[new_left[0]] = b - dista[new_left[0]];
			for (int i = 0; i < (int)new_left.size(); i++) {
				distl[new_left[i]] -= closestUp - location[left[0]] + closestUp - location[new_left[0]];
			}
			left = new_left;
		}
	}
	if (!right.empty()) {
		// handle right side
		int closestDown = c;
		for (int i = 1; i < (int)right.size(); i++) {
			distr[right[i]] = getDistance(right[0], right[i]);
		}
		stype[right[0]] = 2;
		location[right[0]] = b + dista[right[0]] - 2 * (b - d);
		while (1) {
			for (int i = 0; i < (int)right.size(); i++) {
				distr[right[i]] = getDistance(right[0], right[i]);
			}
			vector<int> to_erase;
			for (int i = 1; i < (int)right.size(); i++) {
				if (dista[right[i]] == dista[right[0]] + distr[right[i]]) {
					// to the left of right[0]
					stype[right[i]] = 1;
					location[right[i]] = location[right[0]] - distr[right[i]];
					if (location[closestDown] < location[right[i]]) {
						closestDown = right[i];
					}
					to_erase.pb(i);
				}
			}
			vector<int> new_right;
			for (int i = 1; i < (int)right.size(); i++) {
				if (!binary_search(to_erase.begin(), to_erase.end(), i)) {
					new_right.pb(right[i]);
				}
			}
			if (new_right.empty()) {
				break;
			}
			stype[new_right[0]] = 2;
			location[new_right[0]] = b + dista[new_right[0]] - 2 * (b - d);
			for (int i = 0; i < (int)new_right.size(); i++) {
				distr[new_right[i]] -= location[right[0]] - closestDown + location[new_right[0]] - closestDown;
			}
			right = new_right;
		}
	}
}

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