#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5010;
int dist[maxn][maxn], used[maxn];
int ftype[maxn], loc[maxn];
int n;
int get_closest(int vertex)
{
int closest = -1;
for (int i = 0; i < n; i ++)
{
if (i == vertex)
continue;
if (closest == -1 || dist[vertex][closest] > dist[vertex][i])
closest = i;
}
return closest;
}
void action(int lf, int rf)
{
int closest = -1;
for (int i = 0; i < n; i ++)
{
if (used[i])
continue;
if (closest == -1 || dist[lf][closest] > dist[lf][i])
closest = i;
}
if (closest == -1)
return;
int left_pos_lf = loc[lf] - (dist[lf][closest] - 2 * dist[lf][rf]);
int right_pos_lf = loc[lf] + dist[lf][closest];
int left_pos_rf = loc[rf] - dist[rf][closest];
int right_pos_rf = loc[rf] + (dist[rf][closest] - 2 * dist[lf][rf]);
///cout << "step " << lf << " " << rf << " " << closest << endl;
///cout << "lf " << left_pos_lf << " " << right_pos_lf << endl;
///cout << "rf " << left_pos_rf << " " << right_pos_rf << endl;
if (left_pos_lf == left_pos_rf)
{
loc[closest] = left_pos_lf;
ftype[closest] = 1;
used[closest] = 1;
int to = get_closest(closest);
if (to != rf)
{
loc[to] = loc[closest] + dist[closest][to];
ftype[to] = 2;
used[to] = 1;
action(closest, to);
}
/**for (int i = 0; i < n; i ++)
{
if (!used[i] && dist[closest][i] < loc[lf] - loc[closest])
{
///cout << "use left " << i << " " << closest << " " << lf << endl;
used[i] = 1;
ftype[i] = 2;
loc[i] = loc[closest] + dist[closest][i];
}
}*/
}
else if (right_pos_lf == right_pos_rf)
{
loc[closest] = right_pos_lf;
ftype[closest] = 2;
used[closest] = 1;
int to = get_closest(closest);
if (to != lf)
{
loc[to] = loc[closest] - dist[closest][to];
ftype[to] = 1;
used[to] = 1;
action(to, closest);
}
/**for (int i = 0; i < n; i ++)
{
if (!used[i] && dist[closest][i] < loc[closest] - loc[rf])
{
///cout << "use " << i << endl;
used[i] = 1;
ftype[i] = 1;
loc[i] = loc[closest] - dist[closest][i];
}
}*/
}
else
{
assert(1 == 0);
}
/**cout << "------------------" << endl;
for (int i = 0; i < n; i ++)
cout << loc[i] << " ";
cout << endl;
for (int i = 0; i < n; i ++)
cout << ftype[i] << " ";
cout << endl;*/
action(lf, rf);
}
void findLocation(int N, int first, int location[], int stype[])
{
n = N;
loc[0] = first;
ftype[0] = 1;
used[0] = 1;
if (N == 1)
return;
for (int i = 0; i < N; i ++)
for (int j = i + 1; j < N; j ++)
{
dist[i][j] = dist[j][i] = getDistance(i, j);
}
int closest = get_closest(0);
used[closest] = 1;
ftype[closest] = 2;
loc[closest] = loc[0] + dist[closest][0];
int to = get_closest(closest);
used[to] = 1;
ftype[to] = 1;
loc[to] = loc[closest] - dist[closest][to];
action(to, closest);
for (int i = 0; i < N; i ++)
stype[i] = ftype[i];
for (int i = 0; i < N; i ++)
location[i] = loc[i];
}
