#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
void findLocation(int n, int first, int location[], int stype[]) {
unordered_map<int, int> loc;
unordered_map<int, int> type;
loc[0] = first;
type[0] = 1;
vector<int> dis_0(n);
vector<pii> order;
for (int i = 1; i < n; i++) {
dis_0[i] = getDistance(0, i);
order.emplace_back(dis_0[i], i);
}
sort(order.begin(), order.end());
// min dis is always nearest D to the right
int x = order[0].second;
loc[x] = first + order[0].first;
type[x] = 2;
vector<int> dis_x(n);
dis_x[0] = dis_0[x];
// split into left of 0, in between 0 and x, right of x
vector<pii> left, right;
for (int i = 1; i < n - 1; i++) {
auto [_, y] = order[i];
dis_x[y] = getDistance(x, y);
if (dis_0[y] == dis_0[x] + dis_x[y]) { // left of x
if (dis_x[y] < dis_x[0]) { // in between
loc[y] = loc[x] - dis_x[y];
type[y] = 1;
} else {
left.emplace_back(dis_x[y], y);
}
} else {
right.emplace_back(dis_0[y], y);
}
}
unordered_map<int, int> seen;
sort(right.begin(), right.end());
int r = x; // rightmost D
for (auto [_, y] : right) {
// if y is a C then we should have seen the D used (z) to get to y
int loc_y = loc[r] - getDistance(r, y);
int loc_z = (loc[0] + loc_y + dis_0[y]) / 2;
if (seen.count(loc_z) && type[seen[loc_z]] == 2) {
loc[y] = loc_y;
type[y] = 1;
} else {
loc[y] = loc[0] + dis_0[y];
type[y] = 2;
r = y;
}
seen[loc[y]] = y;
}
sort(left.begin(), left.end());
int l = 0; // leftmost C
for (auto [_, y] : left) {
int loc_y = loc[l] + getDistance(l, y);
int loc_z = (loc[x] + loc_y - dis_x[y]) / 2;
if (seen.count(loc_z) && type[seen[loc_z]] == 1) {
loc[y] = loc_y;
type[y] = 2;
} else {
loc[y] = loc[x] - dis_x[y];
type[y] = 1;
l = y;
}
seen[loc[y]] = y;
}
for (auto [i, loc_i] : loc) {
location[i] = loc_i;
stype[i] = type[i];
}
}
