#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5005;
int mem[maxn][maxn];
int dist(int i, int j){
if(mem[i][j]==-1){
mem[i][j]=getDistance(i,j);
mem[j][i]=mem[i][j];
}
return mem[i][j];
}
void findLocation(int n, int first, int location[], int stype[]) {
for(int i = 0;i<n;i++){
for(int j = 0;j<n;j++){
mem[i][j]=-1;
}
}
location[0]=first;
stype[0]=1;
//base set
array<int,2> dist0[n];
dist0[0]={0,0};
for(int i = 1;i<n;i++){
dist0[i]={dist(0,i),i};
}
sort(dist0,dist0+n);
int rig = dist0[1][1];
int rigd = dist0[1][0];
location[rig]=first+dist0[1][0];
stype[rig]=2;
int fir = rig;
int fird = rigd;
int lef = 0;
assert(dist0[0][0]==0&&dist0[0][1]==0);
int lefd = 0;
for(int i = 2;i<n;i++){
int dr = dist(rig,dist0[i][1]);
int dl = dist(lef,dist0[i][1]);
int d0 = dist(0,dist0[i][1]);
if(d0<=dr+rigd){
//means it is on the left
int dlr = location[rig]-location[lef];
if(dlr+dl==dr){
//went to the right so not new left
location[dist0[i][1]]=location[lef]+dl;
stype[dist0[i][1]]=2;
}
else{
location[dist0[i][1]]=location[rig]-dr;
stype[dist0[i][1]]=1;
lef=dist0[i][1];
lefd=dist0[i][0];
}
}
else{
//means it is on right of right
//so new right discovered
rig=dist0[i][1];
rigd=dist0[i][0];
location[rig]=first+rigd;
stype[rig]=2;
}
}
}
