Submission #139125

#	Time	Username	Problem	Language	Result	Execution time	Memory
139125		muradeyn	Rail (IOI14_rail)	C++14	30 / 100	85 ms	632 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>
#define F first
#define S second

using namespace std;

void findLocation(int N, int first, int location[], int stype[])
{
	location[0] = first;
	stype[0] = 1;
	if (N == 1)return;
	vector< pair<int,int> >v;
	for (int i = 1;i<N;i++) {
		int ret = getDistance(0 , i);
		v.push_back({ret , i});
	}
	sort(v.begin(),v.end());
	int C = 0 , D = (*v.begin()).S;
	location[D] = first + (*v.begin()).F;
	stype[D] = 2;
	set<int>lft , rgt;
	lft.insert(-location[C]);
	rgt.insert(location[D]);
	N--;
	for (int i = 1;i<N;i++) {
		int c = v[i].S;
		int ret1 = getDistance(c , C);
		int ret2 = getDistance(c , D);
		int pos = location[D] - ret2;
		auto it = rgt.lower_bound(pos);
		if (abs(*it - location[C]) + abs(*it - pos) == ret1) {
			location[c] = location[D] - ret2;
			stype[c] = 1;
			if (location[c] < location[C])C = c;
			lft.insert(-location[c]);
			continue;
		}
		pos = location[C] + ret1;
		it = lft.lower_bound(-pos);
		if (abs(*it + location[D]) + abs(*it + pos) == ret2) {
			location[c] = location[C] + ret1;
			stype[c] = 2;
			if (location[c] > location[D])D = c;
			rgt.insert(location[c]);
			continue;
		}
	}
}

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