#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
const int N=5010;
int n, d0[N];
int mem[N][N];
int dist(int i, int j){
if (i==j) return 0;
if (mem[i][j]!=-1) return mem[i][j];
return mem[i][j]=mem[j][i]=getDistance(i, j);
}
void findLocation(int N_, int first, int pos[], int t[])
{
memset(mem, -1, sizeof mem);
n=N_;
for (int i=0; i<n; ++i){
pos[i]=-1;
d0[i]=dist(i, 0);
}
pos[0]=first;
t[0]=1;
int ir=1;
for (int i=1; i<n; ++i) if (d0[i]<d0[ir]) ir=i;
pos[ir]=pos[0]+d0[ir]; t[ir]=2;
int il=0;
vector<int> vl, vr;
for (int i=0; i<n; ++i) if (i!=ir && i!=il){
if (dist(i, il)>dist(i, ir)){
if (dist(i, ir)<dist(il, ir)){
pos[i]=pos[ir]-dist(i, ir);
t[i]=1;
}else vl.push_back(i);
}else{
vr.push_back(i);
}
}
sort(vl.begin(), vl.end(), [&](int x, int y){ return dist(il, x)<dist(il, y); });
sort(vr.begin(), vr.end(), [&](int x, int y){ return dist(il, x)<dist(il, y); });
int ll=il, rr=ir;
for (int i:vr){
int p=(dist(ll, i)-dist(rr, i)+pos[ll]+pos[rr])/2;
if (p==pos[rr]){
pos[i]=pos[rr]-dist(rr, i);
t[i]=1;
}else{
pos[i]=pos[ll]+dist(ll, i);
t[i]=2;
rr=i;
}
}
ll=il, rr=ir;
for (int i:vl){
int p=(dist(ll, i)-dist(rr, i)+pos[ll]+pos[rr])/2;
if (p==pos[ll]){
pos[i]=pos[ll]+dist(ll, i);
t[i]=2;
}else{
pos[i]=pos[rr]-dist(rr, i);
t[i]=1;
ll=i;
}
}
}
