#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
const int TYPE_C = 1, TYPE_D = 2;
const int INF = 1e8;
const int MAX = 5000 + 1;
template <class T1, class T2>
inline bool minimise(T1 &x, T2 y) {
if (x > y) { x = y; return true; }
return false;
}
int N, dist[MAX][MAX];
int getMinIndex(int x) {
int cur_d = INF, y = -1;
for (int i = 0; i < N; i++) if (i != x)
if (minimise(cur_d, dist[x][i]))
y = i;
return y;
}
void findLocation(int _N, int s0, int s[], int t[]) {
N = _N;
s[0] = s0;
t[0] = TYPE_C;
for (int i = 0; i < N; i++) {
dist[i][i] = 0;
for (int j = i + 1; j < N; j++)
dist[i][j] = dist[j][i] = getDistance(i, j);
}
int y = getMinIndex(0);
int x = getMinIndex(y);
s[y] = s[0] + dist[0][y];
t[y] = TYPE_D;
s[x] = s[y] - dist[x][y];
t[x] = TYPE_C;
vector<int> lefts_C = {0, x}, rights_D = {y}, unknowns;
for (int i = 1; i < N; i++) if (i != x and i != y) {
if (dist[x][i] == dist[x][y] + dist[y][i]) {
s[i] = s[y] - dist[y][i];
t[i] = TYPE_C;
lefts_C.push_back(i);
}
else if (dist[y][i] == dist[x][y] + dist[x][i]) {
s[i] = s[x] + dist[x][i];
t[i] = TYPE_D;
rights_D.push_back(i);
}
else
unknowns.push_back(i);
}
for (int i : unknowns) [&]() {
for (int z : lefts_C) {
if (dist[y][i] == dist[y][z] + dist[z][i]) {
s[i] = s[z] + dist[z][i];
t[i] = TYPE_D;
return;
}
}
for (int z : rights_D) {
if (dist[x][i] == dist[x][z] + dist[z][i]) {
s[i] = s[z] - dist[z][i];
t[i] = TYPE_C;
return;
}
}
}();
}
