// ioi 2014
// Day 1: Rail
#include <bits/stdc++.h>
#include "rail.h"
using namespace std;
void findLocation(int N, int first, int location[], int stype[])
{
vector<vector<int>> dist(N, vector<int>(N, 0));
vector<pair<int, int>> closest(N, {0, INT_MAX});
for(int i = 0; i < N - 1; i++) {
for (int j = i + 1; j < N; j++) {
int d = dist[i][j] = dist[j][i] = getDistance(i, j);
if (closest[i].second > d) {
closest[i].second = d;
closest[i].first = j;
}
if (closest[j].second > d) {
closest[j].second = d;
closest[j].first = i;
}
}
}
set<tuple<int, int, int>> pills;
tuple<int, int, int> prime;
for (int i = 0; i < closest.size(); i++) {
if (i < closest[i].first) {
pills.insert({i, closest[i].first, closest[i].second});
}
if (i == 0) {
prime = {i, closest[i].first, closest[i].second};
}
}
pair<int, int> x = {0, first};
pair<int, int> y = {get<1>(prime), get<2>(prime) + first};
for (tuple<int, int, int> pill: pills) {
int a, b, d;
tie(a, b, d) = pill;
// case 1
// x = a and y = b
if (x.first == a and y.first == b) {
location[a] = x.second;
location[b] = y.second;
stype[a] = 1;
stype[b] = 2;
}
// case 2
// x = a
else if (x.first == a) {
location[b] = x.second + d;
stype[b] = 2;
}
// case 3
// y = b
else if (y.first == b) {
location[a] = y.second - d;
stype[a] = 1;
}
// case 4
// x is closer to b than y is closer to a
// hence a, b is right of x, y
else if (dist[x.first][b] < dist[y.first][a]) {
location[b] = x.second + dist[x.first][b];
location[a] = location[b] - d;
stype[a] = 1;
stype[b] = 2;
}
// case 5
// y is closer to a than x is closer to b
// hence a, b is left of x, y
else {
location[a] = y.second - dist[y.first][a];
location[b] = location[a] + d;
stype[a] = 1;
stype[b] = 2;
}
}
}
