#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(int pivot, vector<int> candidate) {
if (candidate.empty()) return;
const int SAME_TYPE = type[pivot];
const int DIFF_TYPE = (type[pivot] == C_STATION)? D_STATION : C_STATION;
const int SIGN = (SAME_TYPE == C_STATION)? +1 : -1;
vector<int> cur;
cur.push_back(candidate.front());
candidate.erase(candidate.begin());
station[cur[0]] = station[pivot] + SIGN * distance(pivot, cur[0]);
type[cur[0]] = DIFF_TYPE;
for (auto i : candidate) {
int turnback = -1;
int last = cur.back();
for (auto c : cur)
if (distance(pivot, i) == distance(pivot, c) + distance(last, i) - SIGN * (station[last] - station[c]))
turnback = c;
if (turnback == -1) {
cur.push_back(i);
type[i] = DIFF_TYPE;
station[i] = station[pivot] + SIGN * distance(pivot, i);
} else {
type[i] = SAME_TYPE;
station[i] = station[pivot] + SIGN * (distance(pivot, i) - 2 * (distance(last, i) - SIGN * (station[last] - station[turnback])));
}
}
}
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;
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);
else
Rside.push_back(i);
}
/* Filter Lside stations from stations that is between pivotC...pivotD */
for (vector<int> tmp; tmp.empty() && !Lside.empty();) {
for (auto i : Lside) {
if (distance(pivotD, i) <= distance(pivotD, pivotC)) {
station[i] = station[pivotD] - distance(pivotD, i);
type[i] = C_STATION;
} else {
tmp.push_back(i);
}
}
Lside = tmp;
break;
}
sort(Rside.begin(), Rside.end(), [&](int l, int r) { return distance(pivotC, l) < distance(pivotC, r); });
sort(Lside.begin(), Lside.end(), [&](int l, int r) { return distance(pivotD, l) < distance(pivotD, r); });
solve(pivotC, Rside);
solve(pivotD, Lside);
for (int i = 0; i < N; i++) stype[i] = type[i];
for (int i = 0; i < N; i++) location[i] = station[i];
return;
}
