#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
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<pair<int,int>>order;
for(int i=1;i<n;i++){
dis_0[i] = getDistance(i,0);
order.emplace_back(dis_0[i], i);
}
sort(order.begin(), order.end());
int x = order[0].second;
loc[x] = first + order[0].first;
type[x] = 2;
vector<int>dis_x;
dis_x[0] = dis_0[x];
vector<pair<int,int>> L, R;
//procesa los demas
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]){ //izq x
if(dis_x[y] < dis_x[0]){ //entre 0 y x
loc[y] = loc[x] - dis_x[y];
type[y] = 1;
}else{ //izq 0
L.emplace_back(dis_x[y], y);
}
}else{ //der equis
R.emplace_back(dis_0[y], y);
}
}
unordered_map<int,int> seen;
sort(R.begin(), R.end());
int r = x; //temp del mas derecho
for(auto[_, y] : R){
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(L.begin(), L.end());
int l = 0; //temp del mas izquierda
for(auto[_, y] : L){
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];
}
}
