#include "rail.h"
#include <bits/stdc++.h>
#define ll long long
#define el cout << endl
#define ii pair<int, int>
#define fi first
#define se second
using namespace std;
const int maxn = 5e3;
const int INF = 1e9;
namespace SUBTASK_1
{
void solve(int n, int first, int location[], int type[])
{
for (int i = 0; i < n; i++)
{
if (i == 0)
{
type[i] = 1;
location[i] = first;
continue;
}
location[i] = getDistance(0, i) + first;
type[i] = 2;
}
}
}
namespace SUBTASK_2
{
void solve(int n, int first, int location[], int type[])
{
ii mn = ii(INF, INF);
for (int i = 0; i < n; i++)
{
if (i == 0)
{
location[0] = first;
type[i] = 1;
continue;
}
mn = min(mn, ii(getDistance(0, i), i));
}
// cout << "OUT!", el;
for (int i = 1; i < n; i++)
{
if (i != mn.se && getDistance(0, mn.se) + getDistance(mn.se, i) == getDistance(0, i))
{
type[i] = 1;
location[i] = first + getDistance(0, mn.se) - getDistance(mn.se, i);
}
else
{
type[i] = 2;
location[i] = first + getDistance(0, i);
}
// cout << "OK: " << i << ' ' << location[i] << ' ' << type[i], el;
}
}
}
namespace SUBTASK_3
{
int dist[maxn + 10][maxn + 10];
void solve(int n, int first, int location[], int type[])
{
type[0] = 1;
location[0] = first;
ii mn = ii(INF, INF);
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
dist[i][j] = dist[j][i] = getDistance(i, j);
for (int j = 1; j < n; j++)
mn = min(mn, ii(dist[0][j], j));
type[mn.se] = 2;
location[mn.se] = first + dist[0][mn.se];
vector<int> lft, rgt;
for (int j = 1; j < n; j++)
{
if (j == mn.se)
continue;
if (dist[0][mn.se] + dist[mn.se][j] == dist[0][j])
lft.push_back(j);
else
rgt.push_back(j);
}
// cout << mn.se, el;
// cout << "LEFT: ";
// for (int x : lft)
// cout << x << ' ';
// el;
// cout << "RIGHT: ";
// for (int x : rgt)
// cout << x << ' ';
// el;
auto check_lft = [&] (int p)
{
for (int x : lft)
{
if (x == p)
continue;
if (dist[0][mn.se] + dist[mn.se][x] + dist[x][p] == dist[0][p])
return x;
}
return -1;
};
auto check_rgt = [&] (int p)
{
for (int x : rgt)
{
if (x == p)
continue;
if (dist[0][x] + dist[x][p] == dist[0][p])
return x;
}
return -1;
};
for (int x : lft)
{
int p = check_lft(x);
if (p == -1)
{
type[x] = 1;
location[x] = first + dist[0][mn.se] - dist[mn.se][x];
}
else
{
type[x] = 2;
location[x] = first + dist[0][mn.se] - dist[mn.se][p] + dist[p][x];
}
}
for (int x : rgt)
{
int p = check_rgt(x);
// cout << x << ' ' << p, el;
if (p == -1)
{
type[x] = 2;
location[x] = first + dist[0][x];
}
else
{
type[x] = 1;
location[x] = first + dist[0][p] - dist[p][x];
}
}
}
};
void findLocation(int n, int first, int location[], int stype[])
{
SUBTASK_3::solve(n, first, location, stype);
}
