#include "rail.h"
#include <vector>
#include <set>
#include <algorithm>
#include <iostream>
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]);
// cerr << location[0] << ' ' << location[X] << '\n';
for(int v = 2; v < N; v++)
{
int Q = lst[v];
// cerr << "computing : " << Q << '\n';
if(dist0[Q] != dist0[X] + distX[Q])
{
// cerr << "case 1\n";
int drq = getDistance(R, Q);
int d = dist0[R] + drq - dist0[Q];
// cerr << "drq = " << drq << '\n';
if(Ds.find(location[R] - d/2) != Ds.end())
{
location[Q] = location[R] - drq;
stype[Q] = typeC;
}
else
{
location[Q] = location[0] + dist0[Q];
stype[Q] = typeD;
}
}
else if(distX[Q] != distX[0] + dist0[Q])
{
// cerr << "case 2\n";
int dlq = getDistance(L, Q);
int d = distX[L] + dlq - distX[Q];
if(Cs.find(location[L] + d/2) != Cs.end())
{
location[Q] = location[L] + dlq;
stype[Q] = typeD;
}
else
{
location[Q] = location[X] - distX[Q];
stype[Q] = typeC;
}
}
else
{
stype[Q] = typeC;
location[Q] = location[X] - distX[Q];
}
if(location[Q] < location[L])
L = Q;
if(location[Q] > location[R])
R = Q;
if(stype[Q] == typeC)
Cs.insert(location[Q]);
else
Ds.insert(location[Q]);
}
// cerr << "computed\n";
// for(int i = 0; i < N; i++) cerr << stype[i] << ' ' << location[i] << '\n';
}
