#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
const int C_STATION = 1;
const int D_STATION = 2;
int N;
vector<int> station, type;
vector<vector<int>> G;
inline int distance(int a, int b) {
if (a == b) G[a][b] = 0;
if (G[a][b] == -1) G[a][b] = G[b][a] = getDistance(a, b);
return G[a][b];
}
void solve_left(int pivotC, int pivotD, vector<int> candidate) {
if (candidate.empty()) return;
sort(candidate.begin(), candidate.end(), [&](int l, int r) {
return distance(pivotD, l) < distance(pivotD, r);
});
vector<int> curC;
for (auto i : candidate) {
bool newC = true;
int turnback = -1;
int lastC = (curC.empty())? 0 : curC.back();
for (auto c : curC)
if (distance(pivotD, i) == distance(pivotD, c) + distance(c, lastC) - distance(lastC, i))
newC = false, turnback = c;
if (newC) {
curC.push_back(i);
station[i] = station[pivotD] - distance(pivotD, i);
type[i] = C_STATION;
} else {
station[i] = station[turnback] + distance(i, lastC) - distance(lastC, turnback);
type[i] = D_STATION;
}
}
}
void solve_right(int pivotC, int pivotD, vector<int> candidate) {
if (candidate.empty()) return;
sort(candidate.begin(), candidate.end(), [&](int l, int r) {
return distance(pivotC, l) < distance(pivotC, r);
});
vector<int> curD;
for (auto i : candidate) {
bool newD = true;
int turnback = -1;
int lastD = (curD.empty())? 0 : curD.back();
for (auto d : curD)
if (distance(pivotC, i) == distance(pivotC, d) + abs(distance(d, lastD) - distance(lastD, i)))
newD = false, turnback = d;
if (newD) {
curD.push_back(i);
station[i] = station[pivotC] + distance(pivotC, i);
type[i] = D_STATION;
} else {
station[i] = station[turnback] - abs(distance(i, lastD) - distance(lastD, turnback));
type[i] = C_STATION;
}
}
}
void solve(int pivotC, int pivotD, vector<int> Lside, vector<int> Rside) {
solve_left(pivotC, pivotD, Lside);
solve_right(pivotC, pivotD, Rside);
return;
}
void findLocation(int N_, int first_, int location[], int stype[]) {
N = N_, station.resize(N), type.resize(N);
G.assign(N, vector<int>(N, -1));
station[0] = first_, type[0] = C_STATION;
int pivotC = 0, pivotD = 1;
for (int i = 0; i < N; i++) if (i != pivotC && distance(pivotC, pivotD) > distance(pivotC, i)) pivotD = i;
station[pivotD] = station[pivotC] + distance(pivotC, pivotD);
type[pivotD] = D_STATION;
for (int i = 0; i < N; i++) if (i != pivotD && distance(pivotD, pivotC) > distance(pivotD, i)) pivotC = i;
station[pivotC] = station[pivotD] - distance(pivotD, pivotC);
type[pivotC] = C_STATION;
vector<int> Lside, Rside;
for (int i = 0; i < N; i++) {
if (i == pivotC || i == pivotD) continue;
if (distance(pivotC, i) == distance(pivotC, pivotD) + distance(pivotD, i)) Lside.push_back(i);
if (distance(pivotD, i) == distance(pivotD, pivotC) + distance(pivotC, i)) Rside.push_back(i);
}
solve(pivotC, pivotD, Lside, Rside);
for (int i = 0; i < N; i++) stype[i] = type[i];
for (int i = 0; i < N; i++) location[i] = station[i];
return;
}
