#include "rail.h"
#include <map>
#include <vector>
#include <algorithm>
#include <iostream>
using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))
int const nmax = 5000;
int const inf = 1000000000;
std::map<std::pair<int,int>, int> cost;
int getcost(int x, int y){
if(cost.find({x, y}) == cost.end())
cost[{y, x}] = cost[{x, y}] = getDistance(x, y);
return cost[{x, y}];
}
struct Train{
int id;
int dist;
bool operator < (Train const &a) const{
return dist < a.dist;
}
};
void findLocation(int N, int first, int location[], int stype[])
{
int pos = 1;
for(int i = 1;i < N; i++)
if(getcost(0, i) < getcost(0, pos))
pos = i;
location[0] = first;
stype[0] = 1;
location[pos] = first + getcost(0, pos);
stype[1] = 2;
std::vector<Train> v;
for(int i = 1; i < N; i++)
if(i != pos)
v.push_back({i, getcost(0, i)});
std::sort(v.begin(), v.end());
int last1 = 0, last2 = pos;
int last3 = 0, last4 = pos;
//std::cout << 0 << " " << location[0] << " " << stype[0] << '\n';
//std::cout << pos << " " << location[pos] << " " << stype[pos] << '\n';
for(int i = 0; i < v.size(); i++){
int id = v[i].id;
if(getcost(0, id) < getcost(pos, id)){
//std::cout << "->";
if((getcost(0, last2) + getcost(last2, id) - 2 * (location[last2] - location[last1])) == getcost(0, id)) {
location[id] = first + getcost(0, id);
stype[id] = 2;
last2 = id;
} else {
location[id] = location[last2] - (getcost(last2, id));
stype[id] = 1;
if(location[last1] < location[id])
last1 = id;
}
} else {
//std::cout << "<-";
int id = v[i].id;
if(getcost(pos, id) < getcost(0, id)){
location[id] = location[pos] - getcost(pos, id);
stype[id] = 1;
} else {
if(getcost(pos, last3) + getcost(last3, id) + 2 * (location[last4] - location[last3]) == getcost(pos, id)){
location[id] = location[pos] - getcost(pos, id);
stype[id] = 1;
last3 = id;
} else {
location[id] = location[last3] + getcost(last3, id);
stype[id] = 2;
if(location[id] < location[last4])
last4 = id;
}
}
}
//std::cout << id << " " << location[id] << " " << stype[id] << '\n';
}
}
