#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5005;
int mem[maxn][maxn];
int dist(int i, int j){
if(mem[i][j]==-1){
mem[i][j]=getDistance(i,j);
mem[j][i]=mem[i][j];
}
return mem[i][j];
}
set<int>typc;
set<int>typd;
int basedon1(int x, int r){
//r->x where r is D, x is D
auto it = typc.upper_bound(x);
if(it!=typc.begin()){
it--;
}
else{
return 1e9;
}
return r-(*it)+x-(*it);
}
int basedon2(int x, int f){
auto it = typd.upper_bound(max(x,f));
if(it==typd.end()){
return 1e9;
}
return (*it)-x+(*it)-f;
}
void findLocation(int n, int first, int location[], int stype[]) {
typc.clear();
typd.clear();
for(int i = 0;i<n;i++){
for(int j = 0;j<n;j++){
mem[i][j]=-1;
}
}
location[0]=first;
stype[0]=1;
typc.insert(first);
//base set
array<int,2> dist0[n];
dist0[0]={0,0};
for(int i = 1;i<n;i++){
dist0[i]={dist(0,i),i};
}
sort(dist0,dist0+n);
int rig = dist0[1][1];
int rigd = dist0[1][0];
location[rig]=first+dist0[1][0];
typd.insert(first+dist0[1][0]);
stype[rig]=2;
int lef = 0;
int lefd = 0;
for(int i = 2;i<n;i++){
int k = dist0[i][1];
int dr = dist(rig,k);
int dl = dist(lef,k);
int d0 = dist(0,k);
//Case 1:
int pos = location[lef]+dl;
if(pos<first){
if(basedon1(pos,location[rig])==dr){
//nice this is good
location[k]=pos;
stype[k]=2;
typd.insert(pos);
continue;
}
}
//Case 2:
pos=location[rig]-dr;
if(pos>first){
if(d0==dl-(first-location[lef])){
if(basedon2(pos,first)==d0&&basedon2(pos,location[lef])==dl){
//valid
location[k]=pos;
stype[k]=1;
typc.insert(pos);
continue;
}
}
}
else{
//Case 3:
if(basedon2(pos,first)==d0){
//valid
assert(pos<location[lef]);
location[k]=pos;
stype[k]=1;
lef=k;
typc.insert(pos);
continue;
}
}
//Case 4:
pos=location[lef]+dl;
location[k]=pos;
stype[k]=2;
assert(pos>location[rig]);
rig=k;
typd.insert(pos);
}
}
