#include <bits/stdc++.h>
#include "rail.h"
#define F first
#define S second
using namespace std;
void findLocation(int N, int first, int location[], int stype[])
{
// id, distance
vector<pair<int, int>> v(N - 1);
for(int i = 1; i < N; ++i) v.at(i - 1) = {i, getDistance(0, i)};
sort(v.begin(), v.end(), [](const auto& a, const auto& b){
return a.S < b.S;
});
int c = 0;
location[c] = first;
stype[c] = 1;
int d = v.at(0).F;
location[d] = location[c] + v.at(0).S;
stype[d] = 2;
for(int i = 1; i < v.size(); ++i){
int cn = getDistance(c, v.at(i).F);
int dn = getDistance(d, v.at(i).F);
if(cn < dn && dn != -1){
location[v.at(i).F] = location[c] + cn;
stype[v.at(i).F] = 2; // D
if(cn > d - c || d == -1) d = v.at(i).F;
}
else{
location[v.at(i).F] = location[d] - dn;
stype[v.at(i).F] = 1; // C
if(dn > d - c || c == -1) c = v.at(i).F;
}
}
return;
}
