#include <bits/stdc++.h>
#include "rail.h"
//#include "grader.h"
using namespace std;
const int MAXN = 5000;
const int INF = 5e8;
int dist[MAXN], poz[MAXN];//dist[i] = distanta de la 0 la i
map<int, int> fr;
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
int i, prc, uld, p, d1, d2, x, cand1, cand2, m, tip;
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) {
fr[location[0]] = 1;
//primul D din dreapta statiei 0
location[poz[1]] = location[0] + dist[poz[1]];
stype[poz[1]] = 2;
fr[location[poz[1]]] = 2;
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);
cand1 = location[prc] + d1;
cand2 = location[uld] - d2;
m = (cand1 + cand2) / 2;
tip = 0;
if (fr.count(m) > 0) {
it = fr.find(m);
tip = it->second;
} else if (m > first) {
tip = 1;
} else {
tip = 2;
}
if (tip != 2) {
//este corect
x = location[p] = location[prc] + d1;
stype[p] = 2;
fr[x] = 2;
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;
fr[x] = 1;
if (x < location[prc]) {
prc = p;
}
}
}
}
}
