#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
// ██╗░░░░░░█████╗░████████╗███████╗ ██████╗░██╗░░░██╗ ░░███╗░░░█████╗░
// ██║░░░░░██╔══██╗╚══██╔══╝██╔════╝ ██╔══██╗╚██╗░██╔╝ ░████║░░██╔══██╗
// ██║░░░░░███████║░░░██║░░░█████╗░░ ██████╦╝░╚████╔╝░ ██╔██║░░██║░░██║
// ██║░░░░░██╔══██║░░░██║░░░██╔══╝░░ ██╔══██╗░░╚██╔╝░░ ╚═╝██║░░██║░░██║
// ███████╗██║░░██║░░░██║░░░███████╗ ██████╦╝░░░██║░░░ ███████╗╚█████╔╝
// ╚══════╝╚═╝░░╚═╝░░░╚═╝░░░╚══════╝ ╚═════╝░░░░╚═╝░░░ ╚══════╝░╚════╝░
// ███╗░░░███╗██╗███╗░░██╗██╗░░░██╗████████╗███████╗░██████╗ ██╗░░██╗
// ████╗░████║██║████╗░██║██║░░░██║╚══██╔══╝██╔════╝██╔════╝ ╚═╝░██╔╝
// ██╔████╔██║██║██╔██╗██║██║░░░██║░░░██║░░░█████╗░░╚█████╗░ ░░░██╔╝░
// ██║╚██╔╝██║██║██║╚████║██║░░░██║░░░██║░░░██╔══╝░░░╚═══██╗ ░░░╚██╗░
// ██║░╚═╝░██║██║██║░╚███║╚██████╔╝░░░██║░░░███████╗██████╔╝ ██╗░╚██╗
// ╚═╝░░░░░╚═╝╚═╝╚═╝░░╚══╝░╚═════╝░░░░╚═╝░░░╚══════╝╚═════╝░ ╚═╝░░╚═╝
#define all(x) (x).begin(), (x).end()
map<int, int> finished;
bool end_or_eq(int k, int v) {
return (finished.find(k) == finished.end() || finished[k] == v);
}
void findLocation(int N, int first, int location[], int stype[]) {
// we already know that
location[0] = first;
stype[0] = 1;
vector<vector<int>> dist(N, vector<int>(N, 0));
dist[0][0] = INT_MAX;
// x and y are two stations right next to each other
// with opposite types
int y = 0;
int x = 0;
int min_d = INT_MAX;
for (int i = 1; i < N; i++) {
int d = dist[0][i] = dist[i][0] = getDistance(0, i);
if (d < min_d) {
x = i;
d = min_d;
}
}
stype[x] = 2;
location[x] = first + min_d;
vector<int> l, r;
for(int i = 1; i < N; i++) {
if (i == x) continue;
dist[x][i] = getDistance(x, i);
bool left = (dist[0][x] + dist[x][i] == dist[0][i]);
if (left && dist[x][i] < dist[0][x]) {
// simplest case: type 'C' left of X
stype[i] = 1;
location[i] = location[x] - dist[x][i];
// better cadidate for y
if (location[y] < location[i]) y = i;
} else if (left) {
l.push_back(i);
} else {
r.push_back(i);
}
}
int c; // corner
int d = (location[y] - location[0]);
for(int i: r) dist[y][i] = dist[0][i] - d;
sort(all(l), [&](int a, int b) {
return dist[x][a] < dist[x][b];
});
sort(all(r), [&](int a, int b) {
return dist[y][a] < dist[y][b];
});
c = l[0];
location[c] = location[x] - dist[x][c];
stype[c] = 1;
finished[location[c]] = stype[c];
for(auto i: l) {
if (i == c) continue;
int d = getDistance(c, i);
if (end_or_eq(location[c] + (dist[x][c] + d - dist[x][i]) / 2, 2)) {
location[i] = location[c] + dist[x][c] - dist[x][i];
stype[i] = 1;
c = i;
} else {
location[i] = location[c] + d;
stype[i] = 2;
}
finished[location[i]] = stype[i];
}
c = r[0];
location[c] = location[y] + dist[y][c];
stype[c] = 2;
finished[location[c]] = stype[c];
for(int i: r) {
if (i == c) continue;
int d = getDistance(c, i);
if (end_or_eq(location[c] - (dist[y][c] + d - dist[y][i]) / 2, 1)) {
location[i] = location[c] - dist[y][c] + dist[y][i];
stype[i] = 2;
c = i;
} else {
location[i] = location[c] - d;
stype[i] = 1;
}
finished[location[i]] = stype[i];
}
}
