#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 5000;
enum RailType {
C,
D
};
struct Station {
int dist1, dist2;
int block;
RailType type;
} v[MAX_N];
vector<int> toright, toleft;
int *location, *stype;
bool cmp1(int a, int b) {
return v[a].dist1 < v[b].dist1;
}
bool cmp2(int a, int b) {
return v[a].dist2 > v[b].dist2;
}
void findLocation(int N, int first, int _location[], int _stype[]) {
int left = 0, right = 1;
location = _location;
stype = _stype;
v[0].block = first;
v[0].type = C;
if(N > 1) {
// get next D rail
for(int i = 1; i < N; ++i) {
v[i].dist1 = getDistance(left, i);
if(v[i].dist1 < v[right].dist1)
right = i;
}
v[right].block = v[left].block + v[right].dist1;
v[right].type = D;
v[left].dist2 = v[right].dist1;
// get distances to right
// also find previous C rail from right
for(int i = 0; i < N; ++i) {
if(i != right && i != left) {
v[i].dist2 = getDistance(right, i);
if(v[i].dist2 < v[left].dist2)
left = i;
}
}
v[left].block = v[right].block - v[left].dist2;
v[left].type = C;
for(int i = 0; i < N; ++i)
v[i].dist1 -= (v[left].block - first);
v[0].dist1 = v[right].block - first + v[right].block - v[left].block;
v[left].dist1 = 0;
for(int i = 0; i < N; ++i)
if(i != left && i != right && v[i].dist1 < v[i].dist2)
toright.push_back(i);
else if(i != left && i != right)
toleft.push_back(i);
sort(toright.begin(), toright.end(), cmp1);
sort(toleft.begin(), toleft.end(), cmp2);
int aux = right;
for(auto it: toright) {
int poz1, poz2, x;
poz2 = v[left].block + v[it].dist1;
poz1 = v[aux].block - (v[it].dist1 - (v[aux].block - v[left].block));
x = getDistance(aux, it);
if(x == v[aux].block - poz1) {
v[it].type = C;
v[it].block = poz1;
} else {
v[it].type = D;
v[it].block = poz2;
aux = it;
}
}
aux = left;
for(auto it: toleft) {
int poz1, poz2, x;
poz2 = v[right].block - v[it].dist2;
poz1 = v[aux].block + (v[it].dist2 - (v[right].block - v[aux].block));
x = getDistance(aux, it);
if(x == poz1 - v[aux].block) {
v[it].type = D;
v[it].block = poz1;
} else {
v[it].type = C;
v[it].block = poz2;
aux = it;
}
}
}
for(int i = 0; i < N; ++i) {
location[i] = v[i].block;
stype[i] = v[i].type + 1;
}
}
