#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5005;
set<int>used;
int n,loc[maxn],sty[maxn];
set<int>valid;
void nova_pochva(int i)
{
int ogr = -1;
int di = 1e9;
if(sty[i]==1)
{
auto it = used.find(loc[i]);
it++;
if(it!=used.end()) ogr = (*it);
}
if(sty[i]==2)
{
auto it = used.find(loc[i]);
if(it!=used.begin())
{
it--;
ogr = (*it);
}
}
if(ogr!=-1) di = abs(loc[i]-ogr);
int minh = 0;
int minch = 1e9;
for(auto it = valid.begin(); it != valid.end(); it++)
{
int house = *it;
int ch = getDistance(i,house);
if(ch<minch)
{
minch = ch;
minh = house;
}
}
if(minch<di)
{
sty[minh] = 3 - sty[i];
loc[minh] = loc[i];
if(sty[i]==1) loc[minh] += minch;
else loc[minh] -= minch;
used.insert(loc[minh]);
valid.erase(minh);
nova_pochva(minh);
}
else nova_pochva(ogr);
}
void findLocation(int N, int first, int location[], int stype[])
{
n = N;
loc[0] = first;
sty[0] = 1;
if(n>1)
{
int mini = 0;
int minch = 1e9;
for(int i = 1; i < n; i++)
{
int ch = getDistance(0,i);
if(ch<minch)
{
minch = ch;
mini = i;
}
}
loc[mini] = loc[0] + minch;
sty[mini] = 2;
for(int i = 1; i < n; i++)
{
if(i==mini) continue;
int ch0 = getDistance(0,i);
int ch1 = getDistance(mini,i);
if(ch0>ch1)
{
sty[i] = 1;
loc[i] = loc[mini] - ch1;
}
else
{
sty[i] = 2;
loc[i] = loc[0] + ch0;
}
}
}
for(int i = 0; i < n; i++) location[i] = loc[i];
for(int i = 0; i < n; i++) stype[i] = sty[i];
}
