Submission #794490

#	Time	Username	Problem	Language	Result	Execution time	Memory
794490		aymanrs	Rail (IOI14_rail)	C++14	100 / 100	51 ms	644 KiB

rail

#include<bits/stdc++.h>
#include <rail.h>
using namespace std;
int getDistance(int i, int j);//{
// 	cout << i << ' ' << j << '\n';
// 	int r;
// 	cin >> r;
// 	return r;
// }
void findLocation(int n, int first, int location[], int stype[]){
	location[0] = first;
	stype[0] = 1;
	if(n == 1) return;
	int d0[n], o[n], d1[n], o1[n], ind = 1;
	d0[0] = 0;
	for(int i = 1;i < n;i++) {
		d0[i] = getDistance(0, i);
		o[i-1] = i;
	}
	sort(o, o+n-1, [&d0](int a, int b){
		return d0[a] < d0[b];
	});
	int s = o[0];
	stype[s] = 2;
	location[s] = first+d0[s];
	d1[0] = d0[s];
	o1[0] = 0;
	d1[s] = 0;
	for(int i = 1;i < n;i++){
		if(i == s) continue;
		o1[ind++] = i;
		d1[i] = getDistance(s, i);
	}
	sort(o1, o1+ind, [&d1](int a, int b){return d1[a] < d1[b];});
	int l2 = s;
	set<int> s2;
	s2.insert(location[s]);
	for(int z = 1;z < n-1;z++){
		int i = o[z];
		if(d0[i] == d0[s]+d1[i]) continue;
		int g = getDistance(l2, i);
		int hp = location[l2]-g;
		int ll2 = *s2.lower_bound(hp+1);
		if(d0[i] != ll2-first+ll2-hp){
			l2 = i;
			location[i] = first+d0[i];
			stype[i] = 2;
			s2.insert(location[i]);
		} else {
			stype[i] = 1;
			location[i] = location[l2]-g;
		}
	}
	l2 = -1;
	first = location[s];
	s2.clear();
	for(int z = 0;z < ind;z++){
		int i = o1[z];
		if(!i){
			l2 = i;
			s2.insert(0);
			continue;
		}
		if(d0[i] < d0[s]+d1[i]) continue;
		if(l2 == -1){
			stype[i] = 1;
			location[i] = first-d1[i];
			l2 = i;
			s2.insert(location[i]);
			continue;
		}
		int g = getDistance(l2, i);
		int hp = location[l2]+g;
		int ll2 = *prev(s2.lower_bound(hp));
		if(d1[i] != first-ll2+hp-ll2){
			l2 = i;
			location[i] = first-d1[i];
			stype[i] = 1;
			s2.insert(location[i]);
		} else {
			stype[i] = 2;
			location[i] = location[l2]+g;
		}
	}
}
// int main(){
// 	int loc[8], typ[8];
// 	findLocation(8, 4, loc, typ);
// }

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