#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
void findLocation(int N, int first, int location[], int stype[]) {
vector<int> d0(N);
for (int i = 1; i < N; ++i) {
d0[i] = getDistance(0, i);
}
int id = 0, mn = INT_MAX;
for (int i = 1; i < N; ++i) {
if (d0[i] < mn) {
id = i;
mn = d0[i];
}
}
stype[0] = 1;
location[0] = first;
stype[id] = 2;
location[id] = location[0] + d0[id];
vector<int> did(N);
did[0] = d0[id];
vector<int> left, right;
for (int i = 1; i < N; ++i) {
if (i == id) {
continue;
}
did[i] = getDistance(id, i);
if (d0[i] == d0[id] + did[i]) {
left.push_back(i);
} else {
right.push_back(i);
}
}
sort(right.begin(), right.end(), [&](int i, int j) {
return d0[i] < d0[j];
});
set<int> f;
int last = id;
f.insert(location[id]);
for (int i : right) {
int d = getDistance(last, i);
int z = abs(d0[i] - d0[last] - d) / 2;
if (f.count(location[last] - z)) {
stype[i] = 1;
location[i] = location[last] - d;
} else {
stype[i] = 2;
location[i] = location[0] + d0[i];
last = i;
f.insert(location[i]);
}
}
last = 0;
f.clear();
f.insert(location[0]);
sort(left.begin(), left.end(), [&](int i, int j) {
return did[i] < did[j];
});
for (int i : left) {
int d = getDistance(last, i);
int z = abs(did[i] - did[last] - d) / 2;
if (f.count(location[last] + z)) {
stype[i] = 2;
location[i] = location[last] + d;
} else {
stype[i] = 1;
location[i] = location[id] - did[i];
last = i;
f.insert(location[i]);
}
}
}
