#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];
}
int fr;
void righter(int first, int lefmost, int location[], int stype[], vector<int>aval){
if(aval.size()==0){
return;
}
vector<int>dists;
for(int i : aval){
dists.push_back(dist(0,i));
}
int mni = min_element(dists.begin(),dists.end())-dists.begin();
int mn = aval[mni];
location[mn]=first+dists[mni];
stype[mn]=2;
vector<int>rig;
for(int i : aval){
if(i==mn){
continue;
}
if(first+dists[mni]-dist(mn,i)>lefmost){
location[i]=first+dists[mni]-dist(mn,i);
stype[i]=1;
}
else{
rig.push_back(i);
}
}
righter(first,location[mn],location,stype,rig);
}
void lefter(int first, int rigmost, int location[], int stype[], vector<int>aval, int init){
if(aval.size()==0){
return;
}
vector<int>dists;
for(int i : aval){
dists.push_back(dist(init,i));
}
int mni = min_element(dists.begin(),dists.end())-dists.begin();
int mn = aval[mni];
location[mn]=first-dists[mni];
stype[mn]=1;
vector<int>lef;
for(int i : aval){
if(i==mn){
continue;
}
if(first-dists[mni]+dist(mn,i)<rigmost){
location[i]=first-dists[mni]+dist(mn,i);
stype[i]=2;
}
else{
lef.push_back(i);
}
}
lefter(first,location[mn],location,stype,lef,init);
}
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;
int dis[n];
dis[0]=0;
for(int i = 1;i<n;i++){
dis[i]=dist(0,i);
}
fr = min_element(dis+1,dis+n)-dis;
location[fr]=first+*min_element(dis+1,dis+n);
stype[fr]=2;
vector<int>rig;
vector<int>lef;
for(int i = 1;i<n;i++) {
if(i==fr){
continue;
}
if(dist(0,i)==dist(0,fr)+dist(fr,i)){
lef.push_back(i);
}
else{
rig.push_back(i);
}
}
righter(first,location[fr],location,stype,rig);
lefter(location[fr],location[fr],location,stype,lef,fr);
}
