#include <bits/stdc++.h>
#include "rail.h"
#warning That's not FB, that's my FB
using namespace std;
int d0[5005];
int d1[5005];
int d;
bool cmp(int x, int y)
{
return d0[x] < d0[y];
}
void findLocation(int n, int first, int location[], int stype[])
{
stype[0] = 1;
location[0] = first;
for (int i = 1; i < n; i++)
d0[i] = getDistance(0,i);
int f, kmin = 1e9;
for (int i = 1; i < n; i++)
{
if (d0[i] < kmin)
f = i, kmin = d0[i];
}
d = kmin;
stype[f] = 2;
location[f] = location[0] + kmin;
for (int i = 1; i < n; i++)
if (i != f)
d1[i] = getDistance(f,i);
vector<int> st,dr;
for (int i = 1; i < n; i++)
{
if (i != f)
{
if (d0[i] < 2 * d and d1[i] < d and d0[i] - d1[i] == d)
{
stype[i] = 1;
location[i] = location[f] - d1[i];
}
else if (d1[i] == d0[i] - d)
st.push_back(i);
else
dr.push_back(i);
}
}
sort(st.begin(), st.end(), cmp);
sort(dr.begin(), dr.end(), cmp);
vector<int> jos;
vector<int> cn_jos;
for (auto it : st)
{
int candi = -1;
for (int i = 0; i < jos.size(); i++)
{
int upb;
if (i == 0)
upb = location[0] - location[jos[i]];
else
upb = location[jos[i - 1]] - location[jos[i]];
upb--;
int dsmin = d1[jos[i]] + 1, dsmax = dsmin + upb - 1;
if (d1[it] >= dsmin and d1[it] <= dsmax)
candi = i;
}
if (candi == -1)
{
stype[it] = 1;
location[it] = location[f] - d1[it];
jos.push_back(it);
cn_jos.push_back(-1);
}
else
{
int loc1 = location[f] - d1[it], loc2 = location[jos[candi]] + (d1[it] - d1[candi]);
///ori e loc1 si in jos, ori e loc2 si in sus
if (cn_jos[candi] == -1)
{
int qq = getDistance(it, jos[candi]);
if (qq == loc2 - location[jos[candi]])
{
cn_jos[candi] = it;
stype[it] = 2;
location[it] = loc2;
}
else
{
stype[it] = 1;
location[it] = location[f] - d1[it];
jos.push_back(it);
cn_jos.push_back(-1);
}
}
else
{
int B = location[cn_jos[candi]] - location[jos[candi]];
if (location[jos[candi]] - loc1 == loc2 - location[jos[candi]])
{
int qq = getDistance(it, jos[candi]);
if (qq == loc2 - location[jos[candi]])
{
stype[it] = 2;
location[it] = loc2;
}
else
{
stype[it] = 1;
location[it] = location[f] - d1[it];
jos.push_back(it);
cn_jos.push_back(-1);
}
}
else
{
int qq = getDistance(it, cn_jos[candi]);
if (qq == location[cn_jos[candi]] - loc1)
{
stype[it] = 1;
location[it] = loc1;
jos.push_back(it);
cn_jos.push_back(-1);
}
else
{
stype[it] = 2;
location[it] = loc2;
}
}
}
}
}
vector<int> sus;
vector<int> cn_sus;
for (auto it : dr)
{
int candi = -1;
for (int i = 0; i < sus.size(); i++)
{
int upb;
if (i == 0)
upb = location[sus[i]] - location[f];
else
upb = location[sus[i]] - location[sus[i - 1]];
upb--;
int dsmin = d1[sus[i]] + 1, dsmax = dsmin + upb - 1;
if (d1[it] >= dsmin and d1[it] <= dsmax)
candi = i;
}
if (candi == -1)
{
stype[it] = 2;
location[it] = d0[it] + location[0];
sus.push_back(it);
cn_sus.push_back(-1);
}
else
{
int loc1 = location[0] + d0[it], loc2 = location[sus[candi]] - (d1[it] - d1[sus[candi]]);
if (cn_sus[candi] == -1)
{
int qq = getDistance(it, sus[candi]);
if (qq == location[sus[candi]] - loc2)
{
cn_sus[candi] = it;
stype[it] = 1;
location[it] = loc2;
}
else
{
location[it] = loc1;
stype[it] = 2;
sus.push_back(it);
cn_sus.push_back(-1);
}
}
else
{
int B = location[sus[candi]] - location[cn_sus[candi]];
if (loc1 - location[sus[candi]] == location[sus[candi]] - loc2)
{
int qq = getDistance(it, sus[candi]);
if (qq == location[sus[candi]] - loc2)
{
stype[it] = 1;
location[it] = loc2;
}
else
{
stype[it] = 2;
location[it] = loc1;
sus.push_back(it);
cn_sus.push_back(-1);
}
}
else
{
int qq = getDistance(it, cn_sus[candi]);
if (qq == loc1 - location[cn_sus[candi]])
{
stype[it] = 2;
location[it] = loc1;
sus.push_back(it);
cn_sus.push_back(-1);
}
else
{
stype[it] = 1;
location[it] = loc2;
}
}
}
}
}
}
/**
d(i,j) = d(j,i) ofc
Iau toate d(0,i) -> d(i); gasesc aia minima, o sa fie prima D in dreapta, fie ea p, si fie d = d(p)
Iau toate d(p,i) -> d2(i); pentru fiecare i != 0 si i != p, e usor de aflat din astea daca e cumva intre 0 si p (si chiar pozitia lui), tipul fiind C
In plus, pentru alea aflate in stanga lui 0, d2(i) o sa fie d1(i) - d, iar daca o sa fie in dreapta, d2(i) o sa fie strict mai mare ca d1(i) - d
Acum, departajand in stanga, fac o chestie dubioasa de le iau crescator, am doua variante (ori un C nou in stanga de tot, ori un D pe undeva stabilit)
Intre alea doua variante stabilesc cu inca un query de distanta
Cred ca ceva de genul ar trebui sa iasa si in dreapta si raman in N - 1 + N - 2 + N - 2 = maxim 3N - 5 query-uri
**/
