#include "rail.h"
#include<bits/stdc++.h>
using namespace std;
int dist[5005][5005];
int query(int i, int j) {
if (dist[i][j]) {
return dist[i][j];
}
dist[i][j] = getDistance(i, j);
return dist[i][j];
}
void findLocation(int n, int f, int loc[], int st[]) {
int l = 0, r, l0, r0;
loc[0] = f;
st[0] = 1;
if (n == 1) {
return;
}
vector<pair<int, int>> ord;
for (int i = 1; i < n; i++) {
ord.push_back({query(0, i), i});
}
sort(ord.rbegin(), ord.rend());
r = ord.back().second;
loc[r] = loc[0]+ord.back().first;
st[r] = 2;
l0 = l;
r0 = r;
ord.pop_back();
while(!ord.empty()) {
auto [_, i] = ord.back();
ord.pop_back();
int ld = query(l, i), rd = query(r, i);
if (max(ld, rd) > loc[r]-loc[l]) {
int l0d = query(l0, i), r0d = query(r0, i);
if (r0d > l0d) {
r = i;
loc[i] = loc[l0]+l0d;
st[i] = 2;
} else {
l = i;
loc[i] = loc[r0]-r0d;
st[i] = 1;
}
}
}
}
