#include <bits/stdc++.h>
#include "rail.h"
using namespace std;
const int INF = 1e8;
struct Station
{
int index, dist;
};
int distFrom0[10000], distFromSP[10000];
int stationType[10000];
int coordLeft[10000], coordRight[10000];
int coord[10000];
vector<Station> leftList, rightList;
bool cmpAsc(const Station &a, const Station &b)
{
return a.dist < b.dist;
}
void findLocation(int n, int firstCoord, int location[], int type[])
{
// Initialisation de la première station
location[0] = firstCoord;
type[0] = 1;
stationType[0] = 2; // point de référence
int spIndex = 0;
int minDist = INF;
// Trouver la station la plus proche de la station 0
for (int i = 1; i < n; i++)
{
distFrom0[i] = getDistance(0, i);
if (distFrom0[i] < minDist)
{
spIndex = i;
minDist = distFrom0[i];
}
}
// Placer cette station à droite
location[spIndex] = firstCoord + distFrom0[spIndex];
type[spIndex] = 2;
stationType[spIndex] = 2;
int cntLeft = 1, cntRight = 1;
coordLeft[cntLeft] = firstCoord;
coordRight[cntRight] = location[spIndex];
// Classer les autres stations en gauche, droite ou indéterminé
for (int i = 1; i < n; i++)
{
if (i == spIndex)
continue;
distFromSP[i] = getDistance(spIndex, i);
if (distFrom0[i] == distFromSP[i] + distFrom0[spIndex])
{
if (distFromSP[i] < distFrom0[spIndex])
{
stationType[i] = 2; // gauche par rapport à spIndex
location[i] = location[spIndex] - distFromSP[i];
type[i] = 1;
coordLeft[++cntLeft] = location[i];
}
else
{
stationType[i] = 1;
}
}
else
{
stationType[i] = 0;
}
}
// Construire les listes gauche/droite
for (int i = 1; i < n; i++)
{
if (stationType[i] == 1)
leftList.push_back({i, distFromSP[i]});
else if (stationType[i] == 0)
rightList.push_back({i, distFrom0[i]});
}
sort(rightList.begin(), rightList.end(), cmpAsc);
sort(leftList.begin(), leftList.end(), cmpAsc);
// Placement des stations à droite
int current = spIndex;
for (auto &st : rightList)
{
int idx = st.index;
int dist0 = st.dist;
if (current == spIndex)
{
location[idx] = firstCoord + dist0;
type[idx] = 2;
current = idx;
coordRight[++cntRight] = location[idx];
}
else
{
int dCur = getDistance(current, idx);
int candCoord = location[current] - dCur;
int minRight = INF;
for (int j = 1; j <= cntRight; j++)
if (coordRight[j] > candCoord)
minRight = min(minRight, coordRight[j]);
if (dist0 == 2 * minRight - candCoord - firstCoord)
{
location[idx] = location[current] - dCur;
type[idx] = 1;
coordLeft[++cntLeft] = location[idx];
}
else
{
location[idx] = firstCoord + dist0;
type[idx] = 2;
current = idx;
coordRight[++cntRight] = location[idx];
}
}
}
current = 0;
for (auto &st : leftList)
{
int idx = st.index;
int distSP = st.dist;
if (current == 0)
{
location[idx] = location[spIndex] - distSP;
type[idx] = 1;
current = idx;
coordLeft[++cntLeft] = location[idx];
}
else
{
int dCur = getDistance(current, idx);
int candCoord = location[current] + dCur;
int maxLeft = 0;
for (int j = 1; j <= cntLeft; j++)
if (coordLeft[j] < candCoord)
maxLeft = max(maxLeft, coordLeft[j]);
if (distSP == candCoord + location[spIndex] - 2 * maxLeft)
{
location[idx] = candCoord;
type[idx] = 2;
coordRight[++cntRight] = location[idx];
}
else
{
location[idx] = location[spIndex] - distSP;
type[idx] = 1;
current = idx;
coordLeft[++cntLeft] = location[idx];
}
}
}
}
