#include <bits/stdc++.h>
#include "rail.h"
using namespace std;
const int maxN = 5005;
int dist[maxN][maxN];
int query(int x, int y) {
if (dist[x][y] != -1) {
return dist[x][y];
}
int val = getDistance(x, y);
dist[x][y] = val;
dist[y][x] = val;
return val;
}
void findLocation(int N, int first, int location[], int stype[])
{
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
dist[i][j] = -1;
}
}
for (int i = 0; i < N; i++) {
dist[i][i] = 0;
}
location[0] = first;
stype[0] = 1;
int bestR = -1;
for (int i = 1; i < N; i++) {
if (bestR == -1 || query(0, i) < query(0, bestR)) {
bestR = i;
}
}
location[bestR] = first + query(0, bestR);
stype[bestR] = 2;
int bestL = 0;
for (int i = 1; i < N; i++) {
if (i == bestR) {
continue;
}
if (query(i, bestR) < query(bestL, bestR)) {
bestL = i;
}
}
location[bestL] = location[bestR] - query(bestL, bestR);
stype[bestL] = 1;
vector <pair <int, int>> right;
vector <pair <int, int>> left;
right.push_back({location[bestR], stype[bestR]});
left.push_back({location[bestL], stype[bestL]});
// cout << bestL << ' ' << bestR << '\n';
for (int i = 0; i < N; i++) {
if (i == bestL || i == bestR) {
continue;
}
if (i == 0) {
left.push_back({location[0], 0});
continue;
}
int d = query(i, bestR);
int d2 = query(bestL, i);
if (d2 == d + dist[bestL][bestR]) { // LEFT
location[i] = location[bestR] - d;
stype[i] = 1;
left.push_back({location[i], i});
// cout << i << ": left\n";
} else { // RIGHT
location[i] = location[bestL] + d2;
stype[i] = 2;
right.push_back({location[i], i});
// cout << i << ": right\n";
}
}
sort(right.begin(), right.end());
// cout << "RIGHT:\n";
// for (auto [p, x] : right) {
// cout << p << ' ' << x << '\n';
// }
int lastR = bestR;
for (int i = 1; i < right.size(); i++) {
auto [pos, x] = right[i];
int d = query(lastR, x);
if (pos - location[lastR] != d) {
lastR = x;
} else {
location[x] = location[lastR] - d;
stype[x] = 1;
}
}
sort(left.begin(), left.end());
reverse(left.begin(), left.end());
int lastL = bestL;
for (int i = 1; i < left.size(); i++) {
auto [pos, x] = left[i];
if (x == 0) {
lastL = 0;
continue;
}
int d = query(lastL, x);
if (location[lastL] - pos != d) {
lastL = x;
} else {
location[x] = location[lastL] + d;
stype[x] = 2;
}
}
// for (int i = 0; i < N; i++) {
// cout << stype[i] << ' ' << location[i] << '\n';
// }
}
