#include "rail.h"
#include "bits/stdc++.h"
#define st first
#define nd second
#define mp make_pair
using namespace std;
struct Station {
int nr, pos, type;
Station(int _nr, int _pos, int _type) {
nr = _nr;
pos = _pos;
type = _type;
}
int distance(int Pos, int Type);
};
vector<Station> stations;
Station findPair(int pos, int type) {
Station res(-1, -1, -1);
for(Station st: stations) {
if(type==0 && st.type==1 && pos < st.pos) {
if(res.nr==-1 || abs(pos - st.pos) < abs(pos - res.pos)) {
res = st;
}
}
if(type==1 && st.type==0 && pos > st.pos) {
if(res.nr==-1 || abs(pos - st.pos) < abs(pos - res.pos)) {
res = st;
}
}
}
//assert(res.nr != -1);
while(res.nr == -1){}
return res;
}
int Station::distance(int Pos, int Type) {
Station paired = findPair(pos, type);
Station Paired = findPair(Pos, Type);
int res = abs(pos - Pos);
if((type==0 && pos > Pos) || (type==1 && pos < Pos)) res += 2*abs(pos - paired.pos);
if((Type==0 && Pos > pos) || (Type==1 && Pos < pos)) res += 2*abs(Pos - Paired.pos);
return res;
}
void findLocation(int N, int first, int location[], int stype[]) {
location[0] = first; stype[0] = 1;
stations.push_back( Station(0, first, 0) );
if(N==1) return;
vector<pair<int, int>> vec(N-1);
for(int i=1; i<N; ++i) {
vec[i-1] = mp(getDistance(0, i), i);
}
sort(vec.begin(), vec.end());
stations.push_back( Station(vec[0].nd, location[0] + vec[0].st, 1) );
Station l = stations[0], r = stations[1];
vec.erase(vec.begin());
for(auto vi: vec) {
int i = vi.nd;
int dl = getDistance(l.nr, i), dr = getDistance(r.nr, i);
vector<Station> cand = {Station(i, l.pos+dl, 1), Station(i, r.pos-dr, 0)};
int cnt_ok = 0;
for(int j=0; j<2; ++j) {
if(l.distance(cand[j].pos, cand[j].type) == dl && r.distance(cand[j].pos, cand[j].type) == dr) {
cnt_ok++;
stations.push_back(cand[j]);
}
}
//assert(cnt_ok == 1);
if(stations.back().pos < l.pos) l = stations.back();
if(stations.back().pos > r.pos) r = stations.back();
}
for(Station st: stations) {
location[st.nr] = st.pos;
stype[st.nr] = st.type+1;
}
return;
}
