#include "rail.h"
#include <map>
#include <vector>
#include <algorithm>
#include <iostream>
#include <fstream>
std::ofstream out ("data.out");
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;
}
};
std::map<int,char> type;
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;
type[location[0]] = 'C';
location[pos] = first + getcost(0, pos);
stype[pos] = 2;
type[location[pos]] = 'D';
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;
for(int i = 0; i < v.size(); i++){
int id = v[i].id;
if(getcost(0, id) < getcost(pos, id)){
int x = location[last2] - getcost(last2, id);
int y = x + (getcost(0, id) - (x - location[0])) / 2;
if(getcost(0, id) == (x - location[0]) + 2 * (y - x) && type[y] == 'D'){
location[id] = x;
stype[id] = 1;
type[location[id]] = 'C';
} else {
location[id] = location[0] + getcost(0, id);
stype[id] = 2;
type[location[id]] = 'D';
}
} else {
int x = location[last1] + getcost(last1, id);
int y = x - (getcost(0, pos) - (location[pos] - x)) / 2;
if(getcost(pos, id) == (location[pos] - x) + 2 * (x - y) && type[y] == 'C'){
location[id] = x;
stype[id] = 2;
type[location[id]] = 'D';
} else {
location[id] = location[pos] - getcost(pos, id);
stype[id] = 1;
type[location[id]] = 'C';
}
}
if(stype[id] == 2 && location[last2] < location[id])
last2 = id;
if(stype[id] == 1 && location[id] < location[last1])
last1 = id;
//std::cout << id << " " << location[id] << " " << stype[id] << '\n';
}
//std::cout << '\n';
/*
for(int i = 0; i < N; i++)
std::cout << stype[i] << " " << location[i] << '\n';
*/
}
/*
2
6
1 3
2 6
2 7
1 1
1 0
2 8
*/
