#include "rail.h"
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
int const NMAX = 5000;
int pos[1 + NMAX];
int type[1 + NMAX];
int dist1[1 + NMAX];
int dist2[1 + NMAX];
int order1[1 + NMAX];
int order2[1 + NMAX];
int origin1, origin2;
int distAux[1 + NMAX];
bool compareOrder1(int a, int b) {
return (dist1[a] < dist1[b]);
}
bool compareOrder2(int a, int b) {
return (dist2[a] < dist2[b]);
}
void buildOrigin(int n, int first) {
origin1 = 0;
pos[origin1] = first;
type[origin1] = 1;
for(int i = 0;i < n;i++) {
order1[i] = i;
if(i != origin1) {
dist1[i] = getDistance(origin1, i);
}
}
sort(order1, order1+n, compareOrder1);
origin2 = order1[1];
pos[origin2] = pos[origin1] + dist1[origin2];
type[origin2] = 2;
dist2[origin1] = dist1[origin2];
for(int i = 0;i < n;i++) {
order2[i] = i;
if(i != origin1 && i != origin2) {
dist2[i] = getDistance(origin2, i);
}
}
sort(order2, order2+n, compareOrder2);
int newOrigin = order2[1];
if(newOrigin != origin1) {
pos[newOrigin] = pos[origin2] - dist2[newOrigin];
type[newOrigin] = 1;
//cerr << pos[origin1] << ' ' << pos[newOrigin] << '\n';
for(int i = 0;i < n;i++) {
if(i == origin1 || dist1[origin2] + dist2[i] == dist1[i]) {
distAux[i] = dist2[newOrigin] + dist2[i];
} else {
distAux[i] = dist1[i] - (pos[newOrigin] - pos[origin1]);
}
}
origin1 = newOrigin;
for(int i = 0;i < n;i++) {
order1[i] = i;
dist1[i] = distAux[i];
}
sort(order1, order1+n, compareOrder1);
}
return;
}
bool isLeft(int station) {
return (dist1[origin2] + dist2[station] == dist1[station]);
}
void solveLeft(int n) {
vector <int> pitstop;
for(int i = 0;i < n;i++) {
int station = order2[i];
if(station != origin1 && station != origin2 && isLeft(station)) {
if(pitstop.size() == 0) {
pitstop.push_back(station);
pos[station] = pos[origin2] - dist2[station];
type[station] = 1;
} else {
int distJ = getDistance(pitstop[pitstop.size()-1], station);
bool isGood = false;
for(int j = pitstop.size()-1;j > 0 && !isGood;j--) {
int indexJ = pitstop[j];
if(dist2[indexJ] + distJ == dist2[station]) {
isGood = true;
pos[station] = pos[indexJ] + distJ;
type[station] = 2;
}
int newJ = pitstop[j-1];
distJ -= (pos[newJ] - pos[indexJ]);
}
if(!isGood) {
int indexJ = pitstop[0];
if(dist2[indexJ] + distJ == dist2[station]) {
pos[station] = pos[indexJ] + distJ;
type[station] = 2;
} else {
pitstop.push_back(station);
pos[station] = pos[origin2] - dist2[station];
type[station] = 1;
}
}
}
}
}
return;
}
void solveRight(int n) {
vector <int> pitstop;
for(int i = 0;i < n;i++) {
int station = order1[i];
if(station != origin1 && station != origin2 && !isLeft(station)) {
if(pitstop.size() == 0) {
pitstop.push_back(station);
pos[station] = pos[origin1] + dist1[station];
type[station] = 2;
} else {
int distJ = getDistance(pitstop[pitstop.size()-1], station);
bool isGood = false;
for(int j = pitstop.size()-1;j > 0 && !isGood;j--) {
int indexJ = pitstop[j];
if(dist1[indexJ] + distJ == dist1[station]) {
isGood = true;
pos[station] = pos[indexJ] - distJ;
type[station] = 1;
}
int newJ = pitstop[j-1];
distJ -= (pos[indexJ] - pos[newJ]);
}
if(!isGood) {
int indexJ = pitstop[0];
if(dist1[indexJ] + distJ == dist1[station]) {
pos[station] = pos[indexJ] - distJ;
type[station] = 1;
} else {
pitstop.push_back(station);
pos[station] = pos[origin1] + dist1[station];
type[station] = 2;
}
}
}
}
}
return;
}
void findLocation(int n, int first, int location[], int stype[]) {
if(n == 1) {
location[0] = first;
stype[0] = 1;
return;
}
buildOrigin(n, first);
solveLeft(n);
solveRight(n);
for(int i = 0;i < n;i++) {
location[i] = pos[i];
stype[i] = type[i];
//cerr << type[i] << ' ' << pos[i] << '\n';
//debug[i] = i;
}
return;
}
