#include "rail.h"
#include <vector>
#include <algorithm>
#define pii pair<int,int>
using namespace std;
int d[5000][5000];
int getDist(int i,int j) {
if (!d[i][j])
d[i][j] = d[j][i] = getDistance(i,j);
return d[i][j];
}
void findLocation(int N, int first, int location[], int stype[])
{
int i; location[0] = first; stype[0] = 1;
vector<pii > v;
for (i = 1; i < N; ++i) {
v.push_back({getDist(0,i),i});
}
sort(v.begin(), v.end());
int r = v[0].second; // right dtype
int l = 0; //left ctype
location[r] = v[0].first + first;
stype[r] = 2;
int fi = r; //first_dtype
for (i = 1, --N; i < N; ++i) {//v_size==N-1
int d0 = v[i].first;
int x = v[i].second;
int df = getDist(x,fi);
if (df < d0) {
if (getDist(0, r) + getDist(r, x) == getDist(0, x)) {
stype[x] = 1;
location[x]=location[r]-getDist(r,x);
}
else {
stype[x] = 2;
location[x] = first + getDist(0,x);
r = x;
}
}
else {
if (getDist(fi, l) + getDist(x, l) == getDist(fi, x)) {
stype[x] = 2;
location[x] = location[l] + getDist(l, x);
}
else {
stype[x] = 1;
location[x] = location[fi] - getDist(fi,x);
l = x;
}
}
}
}
