#include "rail.h"
#define N 5000
#define INF 0x3f3f3f3f
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
int dd[N];
void sort(int *ii, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;
while (j < k)
if (dd[ii[j]] == dd[i_])
j++;
else if (dd[ii[j]] < dd[i_]) {
tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
i++, j++;
} else {
k--;
tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
}
sort(ii, l, i);
l = k;
}
}
void findLocation(int n, int x0, int xx[], int tt[]) {
static int ii1[N], ii2[N];
int n1, n2, i, ir, d_, l, r;
d_ = INF, ir = -1;
for (i = 1; i < n; i++) {
dd[i] = getDistance(0, i);
if (d_ > dd[i])
d_ = dd[i], ir = i;
}
n1 = n2 = 0;
for (i = 0; i < n; i++) {
int d = getDistance(ir, i);
if (i == 0 || i != ir && d_ + d == dd[i])
dd[i] = d, ii1[n1++] = i;
else
ii2[n2++] = i;
}
tt[0] = 1, xx[0] = x0, tt[ir] = 2, xx[ir] = x0 + d_;
sort(ii1, 0, n1);
l = ii1[0], r = ir;
tt[ii1[0]] = 1, xx[ii1[0]] = xx[r] - getDistance(r, ii1[0]);
for (i = 1; i < n1; i++) {
int i_ = ii1[i], d = getDistance(l, i_);
if (d < xx[r] - xx[l]) {
if (dd[l] + d == dd[i_])
tt[i_] = 2, xx[i_] = xx[l] + d, r = i_;
else
tt[i_] = 1, xx[i_] = xx[ir] - dd[i_], l = i_;
} else {
if (dd[l] + d == dd[i_] + (xx[r] - xx[l]) * 2)
tt[i_] = 1, xx[i_] = xx[ir] - dd[i_], l = i_;
else
tt[i_] = 2, xx[i_] = xx[l] + d;
}
}
sort(ii2, 0, n2);
l = 0, r = ii2[0];
tt[ii2[0]] = 2, xx[ii2[0]] = xx[l] + getDistance(l, ii2[0]);
for (i = 1; i < n2; i++) {
int i_ = ii2[i], d = getDistance(r, i_);
if (d < xx[r] - xx[l]) {
if (dd[r] + d == dd[i_])
tt[i_] = 1, xx[i_] = xx[r] - d, l = i_;
else
tt[i_] = 2, xx[i_] = xx[0] + dd[i_], r = i_;
} else {
if (dd[r] + d == dd[i_] + (xx[r] - xx[l]) * 2)
tt[i_] = 2, xx[i_] = xx[0] + dd[i_], r = i_;
else
tt[i_] = 1, xx[i_] = xx[r] - d;
}
}
}
