#include "rail.h"
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
using vi = vector<int>;
const int mx = 5'000;
int X;
vi dist0(mx);
vi distX(mx);
const int typeC = 1;
const int typeD = 2;
void findLocation(int N, int first, int location[], int stype[])
{
dist0[0] = 0;
for(int i = 1; i < N; i++)
{
dist0[i] = getDistance(0, i);
}
int lst[N];
for(int i = 0; i < N; i++)
lst[i] = i;
sort(lst, lst+N, [] (int u, int v)
{
return dist0[u] < dist0[v];
});
X = lst[1];
location[0] = first;
stype[0] = typeC;
location[X] = first + dist0[X];
stype[X] = typeD;
int L = 0;
int R = X;
for(int i = 0; i < N; i++)
{
if(i == 0) distX[0] = dist0[X];
else if(i == X) distX[X] = 0;
else distX[i] = getDistance(X, i);
}
set<int> Cs;
set<int> Ds;
Cs.insert(location[0]);
Ds.insert(location[X]);
for(int v = 2; v < N; v++)
{
int Q = lst[v];
if(dist0[X] + distX[Q] != dist0[Q])
{
int d = dist0[R] + getDistance(R, Q) - dist0[Q];
if(Cs.find(location[R] - d/2) != Cs.end())
{
location[Q] = first + dist0[Q];
stype[Q] = typeD;
R = Q;
}
else
{
location[Q] = (location[R] - d/2) - (dist0[Q] - (location[R] - d/2 - first));
stype[Q] = typeC;
}
}
else if(distX[0] + dist0[Q] != distX[Q])
{
int d = distX[L] + getDistance(L, Q) - distX[Q];
if(Ds.find(location[L] + d/2) != Ds.end())
{
location[Q] = location[X] - distX[Q];
stype[Q] = typeC;
L = Q;
}
else
{
location[Q] = (location[L] + d/2) + (distX[Q] - (location[X] - (location[L] + d/2)));
stype[Q] = typeD;
}
}
else
{
location[Q] = first + dist0[Q];
stype[Q] = typeD;
}
if(stype[Q] == typeC)
Cs.insert(location[Q]);
else
Ds.insert(location[Q]);
}
}
