#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){
location[v.at(i).F] = location[c] + cn;
stype[v.at(i).F] = 2; // D
if(cn > d - c) d = v.at(i).F;
}
else if(cn > dn){
location[v.at(i).F] = location[d] - dn;
stype[v.at(i).F] = 1; // C
if(dn > d - c) c = v.at(i).F;
}
else{
int mid = (d + c) / 2;
int type = 0;
for(int j = i - 1; j >=0; --j) if(v.at(j).F == mid) type = stype[v.at(j).F];
if(type == 1){
location[v.at(i).F] = location[c] + cn;
stype[v.at(i).F] = 2; // D
if(cn > d - c) 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 = v.at(i).F;
}
}
}
return;
}
