#include "rail.h"
//#include "grader.cpp"
#include <set>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
const int MAXN = 5005;
int askedAlready[MAXN][MAXN];
int ask(int x, int y)
{
if(x>y) swap(x, y);
if(askedAlready[x][y]==-1) askedAlready[x][y] = getDistance(x, y);
return askedAlready[x][y];
}
int loc[MAXN];
set <int> allPositions[5];
int solveCase1(int l, int r, int k)
{
int posK = loc[l] + ask(l, k);
int posP = (loc[r] + posK - ask(r, k))/2;
if((loc[r] + posK - ask(r, k))%2!=0) return -1;
if(posP<=loc[r] && allPositions[1].count(posP)==true && posK<loc[r]) return posK;
return -1;
}
int solveCase2(int l, int r, int k)
{
int posK = loc[l] + ask(l, k);
int posP = (loc[r] + posK - ask(r, k))/2;
if((loc[r] + posK - ask(r, k))%2!=0) return -1;
//cout << posP << '\n';
if(posP<=loc[r] && allPositions[1].count(posP)==true && posK>loc[r]) return posK;
return -1;
}
int solveCase3(int l, int r, int k)
{
int posK = loc[r] - ask(r, k);
int posP = (loc[l] + posK + ask(l, k))/2;
if(posP>=loc[l] && allPositions[2].count(posP)==true && posK<loc[l]) return posK;
return -1;
}
int solveCase4(int l, int r, int k)
{
int posK = loc[r] - ask(r, k);
int posP = (loc[l] + posK + ask(l, k))/2;
// cout << posP << '\n';
if(posP>=loc[l] && allPositions[2].count(posP)==true && posK>loc[l]) return posK;
return -1;
}
void findLocation(int N, int first, int location[], int stype[])
{
memset(askedAlready, -1, sizeof(askedAlready));
vector <int> order;
for(int i = 1;i<N;i++) order.push_back(i);
sort(order.begin(), order.end(),
[&](int a, int b)
{
if(ask(0, a)<ask(0, b)) return true;
return false;
});
int l = 0;
loc[0] = first;
stype[0] = 1;
allPositions[1].insert(loc[l]);
int r = order[0];
loc[ order[0] ] = first + ask(0, order[0]);
stype[ order[0] ] = 2;
allPositions[2].insert(loc[r]);
for(int iter = 1;iter<order.size();iter++)
{
int val = -1;
//cout << order[iter] << " || " << l << " " << r << '\n';
val = solveCase1(l, r, order[iter]);
if(val!=-1)
{
//cout << "CASE 1" << '\n';
loc[ order[iter] ] = val;
stype[ order[iter] ] = 2;
allPositions[ stype[ order[iter] ] ].insert(val);
continue;
}
val = solveCase2(l, r, order[iter]);
if(val!=-1)
{
//cout << "CASE 2" << '\n';
loc[ order[iter] ] = val;
stype[ order[iter] ] = 2;
allPositions[ stype[ order[iter] ] ].insert(val);
r = order[iter];
continue;
}
val = solveCase3(l, r, order[iter]);
if(val!=-1)
{
loc[ order[iter] ] = val;
stype[ order[iter] ] = 1;
allPositions[ stype[ order[iter] ] ].insert(val);
l = order[iter];
continue;
}
val = solveCase4(l, r, order[iter]);
if(val!=-1)
{
loc[ order[iter] ] = val;
stype[ order[iter] ] = 1;
allPositions[ stype[ order[iter] ] ].insert(val);
continue;
}
//cout << order[iter] << " -> FAK" << '\n';
}
for(int i = 0;i<N;i++)
{
location[i] = loc[i];
//cout << i << " -> " << stype[i] << " " << location[i] << '\n';
}
}
