#include "rail.h"
#include <algorithm>
#include <vector>
const int MAXN = 5e3;
int dist0[MAXN];
int distA[MAXN];
std::vector<int> left, right;
void findLocation(int N, int first, int location[], int stype[])
{
location[0] = first;
stype[0] = 1;
for (int iSta = 1; iSta < N; iSta++)
dist0[iSta] = getDistance(0, iSta);
int stationA = std::min_element(dist0 + 1, dist0 + N) - dist0;
location[stationA] = location[0] + dist0[stationA];
stype[stationA] = 2;
distA[0] = dist0[stationA];
for (int iSta = 1; iSta < N; iSta++)
if (iSta != stationA)
{
distA[iSta] = getDistance(stationA, iSta);
if (dist0[iSta] == dist0[stationA] + distA[iSta])
left.emplace_back(iSta);
else
right.emplace_back(iSta);
}
std::sort(right.begin(), right.end(), [](int a, int b) { return (dist0[a] < dist0[b]); });
int lastD = -1;
for (int iSta = 0; iSta < (int)right.size(); iSta++)
{
int station = right[iSta];
location[station] = location[0] + dist0[station];
stype[station] = 2;
if (lastD != -1)
{
int distLast = getDistance(lastD, station);
for (int jSta = 0; jSta < iSta; jSta++)
{
int stat2 = right[jSta];
if (stype[stat2] == 2 && distLast - (location[lastD] - location[stat2]) == dist0[station] - (location[stat2] - location[0]))
{
location[station] = location[stat2] - dist0[station] + (location[stat2] - location[0]);
stype[station] = 1;
break;
}
}
}
if (stype[station] == 2)
lastD = station;
}
std::sort(left.begin(), left.end(), [](int a, int b) { return (distA[a] < distA[b]); });
int lastC = -1;
for (int iSta = 0; iSta < (int)left.size(); iSta++)
{
int station = left[iSta];
location[station] = location[stationA] - distA[station];
stype[station] = 1;
if (lastC != -1)
{
int distLast = getDistance(lastC, station);
for (int jSta = 0; jSta < iSta; jSta++)
{
int stat2 = left[jSta];
if (stype[stat2] == 1 && distLast - (location[stat2] - location[lastC]) == distA[station] - (location[stationA] - location[stat2]))
{
location[station] = location[stat2] + distA[station] - (location[stationA] - location[stat2]);
stype[station] = 2;
break;
}
}
}
if (stype[station] == 1)
lastC = station;
}
}
