#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
const int nx = 5005;
int n;
vector<pair<int,int>> A, B, C; // A = left of 0, B = right of X
int dist0[nx], distX[nx], dist[nx][nx];
bool vis[nx];
int pos[1000006];
void findLocation(int N, int first, int location[], int stype[]) {
n = N;
memset(pos, -1, sizeof pos);
location[0] = first;
stype[0] = 1;
pos[first] = 0;
for (int i = 1; i < N; i++) {
dist0[i] = getDistance(0, i);
C.emplace_back(dist0[i], i);
}
sort(C.begin(), C.end());
int dx = C[0].first, x = C[0].second;
location[x] = first + dx;
stype[x] = 2;
vis[0] = vis[x] = 1;
pos[location[x]] = x;
for (int i = 1; i < N; i++) {
if (vis[i]) continue;
distX[i] = getDistance(x, i);
//cout << distX[i] << " ";
} //cout << x << "\n";
for (int i = 0; i < N; i++) {
if (vis[i]) continue;
if (distX[i] < dist0[x]) {
location[i] = first + dist0[x] - distX[i];
stype[i] = 1;
vis[i] = 1;
pos[location[i]] = i;
} else if (dist0[i] == dist0[x] + distX[i]) {
A.emplace_back(dist0[i], i);
} else {
B.emplace_back(dist0[i], i);
}
}
sort(A.begin(), A.end());
sort(B.begin(), B.end());
// Process B
int lastD = x;
for (auto [d, idx] : B) {
if (vis[idx]) continue;
d = getDistance(lastD, idx);
if (stype[pos[location[lastD] - (dist0[lastD] + d - dist0[idx]) / 2]] == 2) {
location[idx] = location[lastD] - d;
stype[idx] = 1;
vis[idx] = 1;
} else {
location[idx] = first + dist0[idx];
stype[idx] = 2;
vis[idx] = 1;
lastD = idx;
}
pos[location[idx]] = idx;
}
//cout << "\n----\n";
if (A.empty()) {
return;
}
int lastC = A[0].second;
location[lastC] = first + dist0[x] - distX[lastC];
stype[lastC] = 1;
vis[lastC] = 1;
pos[location[lastC]] = lastC;
for (auto [d, idx] : A) {
if (vis[idx]) continue;
d = getDistance(lastC, idx);
if (stype[pos[location[lastC] + (distX[lastC] + d - distX[idx]) / 2]] == 1) {
//cout << idx << " " << lastC << "\n";
location[idx] = location[lastC] + d;
stype[idx] = 2;
vis[idx] = 1;
} else {
//cout << idx << " " << lastC << endl;
location[idx] = location[x] - distX[idx];
stype[idx] = 1;
vis[idx] = 1;
lastC = idx;
}
pos[location[idx]] = idx;
}
/*for (int i = 0; i < N; i++) {
cout << location[i] << " ";
} cout << endl;
for (int i = 0; i < N; i++) {
cout << stype[i] << " ";
} cout << endl;*/
}
/*
Edited tc:
1
4
1 1
2 7
2 4
2 9
2
8
1 3
2 6
1 7
1 1
1 0
2 8
2 2
1 4
*/
