#include "rail.h"
#include <vector>
#include <iostream>
#include <set>
#include <queue>
#include <algorithm>
#include <cassert>
using namespace std;
typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define MAX_N (1<<19)
#define INF 1145141919
#define all(x) x.begin(), x.end()
#define pb push_back
#define _1 first
#define _2 second
int memo[5000][5000];
int query(int a, int b) {
if (memo[a][b] != -1) return memo[a][b];
return memo[a][b] = getDistance(a, b);
}
void findLocation(int N, int first, int location[], int stype[]) {
rep(i, N) rep(j, N) memo[i][j] = -1;
rep(i, N) memo[i][i] = 0;
P m = P(INF, -1);
rep(i, N) if (i != 0) m = min(m, P(query(0, i), i));
int a = m._2;
m = P(INF, -1);
rep(i, N) if (i != a) m = min(m, P(query(a, i), i));
int b = m._2;
location[0] = first;
location[a] = location[0] + query(0, a);
location[b] = location[a] - query(a, b);
stype[a] = 2;
stype[b] = 1;
vector<P> ps;
rep(i, N) if (i != a && i != b) ps.pb(P(query(a, i), i));
sort(all(ps));
vector<int> ls, rs;
for (P pp : ps) {
int i = pp._2, k = -1;
if (query(a, i) < query(b, i)) {
// left
for (int p : ls) {
if (query(p, i) + query(a, p) == query(a, i)) {
k = p;
break;
}
}
if (k == -1) {
stype[i] = 1;
location[i] = location[a] - pp._1;
ls.pb(i);
}
else {
stype[i] = 2;
location[i] = location[a] - (pp._1 - query(k, i)*2);
}
}
else {
// right
for (int p : rs) {
if (query(b, p) + query(p, i) == query(b, i)) {
k = p;
break;
}
}
if (k == -1) {
stype[i] = 2;
location[i] = location[b] + pp._1 - query(a, b);
rs.pb(i);
}
else {
stype[i] = 1;
location[i] = location[b] + (pp._1 - query(a, b) - query(k, i)*2);
}
}
}
}
