Submission #496954

#	Time	Username	Problem	Language	Result	Execution time	Memory
496954		Temmie	Rail (IOI14_rail)	C++17	100 / 100	85 ms	8272 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>

void findLocation(int n, int first, int location[], int stype[]) {
	location[0] = first, stype[0] = 1;
	if (n == 1) {
		return;
	}
	std::vector <int> inv(int(2e6) + 3, -1);
	inv[first] = 0;
	std::vector <std::pair <int, int>> a(n - 1);
	for (int i = 1; i < n; i++) {
		a[i - 1] = { getDistance(0, i), i };
	}
	std::sort(a.rbegin(), a.rend());
	int l = 0, r = a.back().second;
	location[r] = first + a.back().first;
	stype[r] = 2;
	inv[location[r]] = r;
	a.pop_back();
	while (a.size()) {
		int ind = a.back().second;
		a.pop_back();
		int left = getDistance(l, ind);
		int right = getDistance(r, ind);
		int loc1 = location[l] + left;
		int loc2 = location[r] - right;
		int mid = (loc1 + loc2) >> 1;
		if (inv[mid] == -1) {
			stype[ind] = first < mid ? 2 : 1;
		} else {
			stype[ind] = stype[inv[mid]] == 1 ? 2 : 1;
		}
		location[ind] = stype[ind] == 1 ? loc2 : loc1;
		inv[location[ind]] = ind;
		if (location[ind] > location[r]) {
			r = ind;
		} else if (location[ind] < location[l]) {
			l = ind;
		}
	}
}

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