Submission #496935

#	Time	Username	Problem	Language	Result	Execution time	Memory
496935		Temmie	Rail (IOI14_rail)	C++17	0 / 100	67 ms	716 KiB

rail

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

//int getDistance(int i, int j) {
	//return 0;
//}

void findLocation(int n, int first, int location[], int stype[]) {
	location[0] = first, stype[0] = 1;
	if (n == 1) {
		return;
	}
	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 = first, r = a.back().second;
	location[r] = first + a.back().first;
	stype[r] = 2;
	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 (first < mid) {
			stype[ind] = 2;
		} else {
			stype[ind] = 1;
		}
		if (stype[ind] == 1) {
			std::swap(loc1, loc2);
		}
		location[ind] = loc1;
		if (loc1 > location[r]) {
			r = loc1;
		} else if (loc1 < location[l]) {
			l = loc2;
		}
	}
}

//int main() {
	
//}

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