#include <bits/stdc++.h>
#include "rail.h"
using namespace std;
int d[5001][5001];
int ask(int i,int j){
if(i==j)return 0;
if(d[i][j])return d[i][j];
d[i][j] = d[j][i] = getDistance(i,j);
return d[i][j];
}
void findLocation(int n, int f, int location[], int stype[])
{
location[0] = f;
stype[0] = 1;
//find the closest guy to 0
int mnn = 1e9;
int x = 0;
vector<int>l,r;
for(int i=1;i<n;i++){
if(mnn > ask(0,i)){
mnn = ask(0,i);
x = i;
}
}
stype[x] = 2;
location[x] = f + ask(0,x);
for(int i=0;i<n;i++){
if(i!=0 && i!=x){
if(ask(0,i) == ask(0,x) + ask(x,i))l.push_back(i);
else r.push_back(i);
}
}
vector<pair<int,int>>a;
for(int y:r)a.push_back({ask(0,y),y});
sort(a.begin(),a.end());
int last = x;
map<int,bool>seen;
for(auto Z : a){
int z = Z.second;
//try the path x->y->z
//will always be a upper bound to x->z
int m = ask(0,last) + ask(last,z);
m-=ask(0,z);
m/=2;
if(location[last] - m>=0 && seen[location[last] - m]){
stype[z] = 1;
location[z] = location[last] - ask(last,z);
}else{
stype[z] = 2;
location[z] = location[0] + ask(0,z);
seen[location[z]] = 1;
last = z;
}
}
a.clear();
seen.clear();
for(int y:l)a.push_back({ask(x,y),y});
sort(a.begin(),a.end());
last = 0;
for(auto Z : a){
int z = Z.second;
int m = ask(x,last) + ask(last,z);
m-=ask(x,z);
m/=2;
if(location[last] + m <= 1000000 && seen[location[last] + m]){
stype[z] = 2;
location[z] = location[last] + ask(last,z);
}else{
stype[z] = 1;
location[z] = location[x] - ask(x,z);
last = z;
seen[location[z]] = 1;
}
}
//for(int i=0;i<n;i++)cout<<stype[i]<<" "<<location[i]<<'\n';
}
