#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;
}
int findDistToZero(int type, int poz, int poz0, vector <int> &known, int stype[], int location[]) {
if (type == 2 && poz > poz0) {
return poz - poz0;
}
if (type == 1) {
int d = 1e9;
for (int x : known) {
if (stype[x] == 2 && location[x] > max(poz, poz0)) {
d = min(d, 2 * location[x] - poz - poz0);
}
}
return d;
}
int bestL = -1, bestR = -1;
for (int x : known) {
if (stype[x] == 1) {
if (location[x] > poz) {
continue;
}
if (bestL == -1 || location[x] > location[bestL]) {
bestL = x;
}
} else if (stype[x] == 2) {
if (location[x] < poz0) {
continue;
}
if (bestR == -1 || location[x] < location[bestR]) {
bestR = x;
}
}
}
// cout << bestL << ' ' << bestR << '\n';
// cout << poz << ' ' << location[bestL] << ' ' << location[bestR] << '\n';
return location[bestR] - poz0 + location[bestR] - location[bestL] + poz - location[bestL];
}
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 best = -1;
for (int i = 1; i < N; i++) {
if (best == -1 || query(0, i) < query(0, best)) {
best = i;
}
}
location[best] = location[0] + query(0, best);
stype[best] = 2;
vector <pair <int, int>> v;
for (int i = 1; i < N; i++) {
if (best == i) {
continue;
}
v.push_back({dist[0][i], i});
}
sort(v.begin(), v.end());
int l = 0, r = best;
vector <int> known = {0, best};
// for (int x : known) {
// cout << x << ' ' << location[x] << ' ' << stype[x] << '\n';
// }
for (int i = 0; i < v.size(); i++) {
auto [d, x] = v[i];
// cout << x << '\n';
// cout << "KNOWN:\n";
// for (int y : known) {
// cout << y << ' ' << location[y] << ' ' << stype[y] << '\n';
// }
// cout << '\n';
int distToLeft = query(l, x);
int distToRight = query(x, r);
// cout << x << ' ' << distToLeft << ' ' << distToRight << '\n';
/// CHECKING STYPE = 1:
bool ok = 0;
location[x] = location[r] - distToRight;
for (int y : known) {
if (stype[y] == 1) {
continue;
}
if (location[y] < location[x]) {
continue;
}
// cout << "Trying: ";
// cout << y << ' ' << location[y] - location[l] + location[y] - location[x] << '\n';
if (location[y] - location[l] + location[y] - location[x] == distToLeft) {
ok = 1;
}
}
if (ok) {
if (location[x] < location[l]) {
l = x;
}
// cout << "Solution 1 for " << x << '\n';
known.push_back(x);
stype[x] = 1;
continue;
}
/// CHECKING STYPE = 2
location[x] = location[l] + distToLeft;
for (int y : known) {
if (stype[y] == 2) {
continue;
}
if (location[y] > location[x]) {
continue;
}
if (location[r] - location[y] + location[x] - location[y] == distToRight) {
ok = 1;
}
}
if (ok) {
if (location[x] > location[r]) {
r = x;
}
// cout << "Solution 2 for " << x << '\n';
known.push_back(x);
stype[x] = 2;
continue;
}
int test1 = findDistToZero(1, location[r] - distToRight, first, known, stype, location);
int test2 = findDistToZero(2, location[l] + distToLeft, first, known, stype, location);
// if (x == 3) {
// cout << "Values:\n";
// cout << l << ' ' << location[l] << ' ' << distToLeft << '\n';
// cout << "Left: " << l << ' ' << location[l] << '\n';
// cout << "Right: " << r << ' ' << location[r] << '\n';
// cout << test1 << ' ' << test2 << ' ' << query(0, x) << '\n';
// }
if (test2 == query(0, x)) {
stype[x] = 2;
location[x] = location[l] + distToLeft;
if (location[x] > location[r]) {
r = x;
}
} else if (test1 == query(0, x)) {
stype[x] = 1;
location[x] = location[r] - distToRight;
if (location[x] < location[r]) {
l = x;
}
} else {
exit(-1);
}
// cout << "Emergency for " << x << '\n';
known.push_back(x);
// exit(-1);
}
// for (int i = 0; i < N; i++) {
// cout << stype[i] << ' ' << location[i] << '\n';
// }
}
