#include <bits/stdc++.h>
#include "rail.h"
using namespace std;
const int MAXN = 5000;
int dist[MAXN], poz[MAXN];//dist[i] = distanta de la 0 la i
//set
map<int, int> frc;
map<int, int> frd;
map<int, int>::iterator it;
char cmp(int a, int b) {
return dist[a] < dist[b];
}
int minim(int a, int b) {
return a < b ? a : b;
}
int maxim(int a, int b) {
return a > b ? a : b;
}
void findLocation(int n, int first, int location[], int stype[]) {
//primul va fi C si ultimul D
//le sortez crescator dupa distanta pana la statia 0
//cea mai mica distanta va fi catre primul D din dreapta statiei 0
//dupa la fiecare pas tin cel mai din stanga C si cel mai din dreapta D de pana acum
//si pentru fiecare aflu distanta pana la acestea 2 si stiu ca unul dintre ele are drumul minim pana la el fara sa treaca prin alte statii
//deci doar verific cele 2 cazuri ca sa imi dau seama unde este noua statie
int i, prc, uld, p, d1, d2, x, a, d3;
dist[0] = poz[0] = 0;
location[0] = first;
stype[0] = 1;
for (i = 1; i < n; i++) {
dist[i] = getDistance(0, i);
poz[i] = i;
}
sort(poz, poz + n, cmp);
if (n > 1) {
frc[location[0]] = 1;
//primul D din dreapta statiei 0
location[poz[1]] = location[0] + dist[poz[1]];
stype[poz[1]] = 2;
frd[location[poz[1]]] = 1;
prc = 0;
uld = poz[1];
for (i = 2; i < n; i++) {
//este logic ca nu poate respecta ambele conditii doar cu d1 si d2
//daca este D si se ajunge direct de la prc
p = poz[i];
d1 = getDistance(prc, p);
d2 = getDistance(uld, p);
x = location[prc] + d1;//locatia daca ar fi D
it = frc.lower_bound(minim(location[uld], x));//C-ul pe care il iau ca sa ajung la p
it--;
a = it->first;
d3 = location[uld] - a + x - a;
if (d3 == d2) {
//este corect
location[p] = x;
stype[p] = 2;
frd[x] = 1;
if (x > location[uld]) {
uld = p;
}
} else {
//inseamna ca se ajunge direct din uld deci este statie de tip C
x = location[p] = location[uld] - d2;
stype[p] = 1;
frc[x] = 1;
if (x < location[prc]) {
prc = p;
}
}
}
}
}
