# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
236205 | Bilyana | Rail (IOI14_rail) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
const int MAXN = 5000;
int dist[MAXN];
int ldist[MAXN], rdist[MAXN];
int wh[MAXN];
bool ch[MAXN];
struct cmpl {
bool operator()(int l, int r) {
return ldist[l] < ldist[r];
}
};
struct cmpr {
bool operator()(int l, int r) {
return rdist[l] < rdist[r];
}
};
void findLocation(int n, int first, int location[], int stype[])
{
location[0] = first;
stype[0] = 1;
ch[0] = 1;
for (int i=1; i<n; i++) {
dist[i] = getDistance(0, i);
wh[i] = i;
}
int mn = dist[1], m = 1;
for (int i=2; i<n; i++) {
if (mn > dist[i]) {
m = i;
mn = dist[i];
}
}
location[wh[m]] = first + dist[wh[m]];
stype[wh[m]] = 2;
ch[wh[m]] = 1;
for (int i=0; i<n; i++) {
if (ch[i]) {
ldist[i] = 1e6;
rdist[i] = 1e6;
continue;
}
int temp = getDistance(i, m);
if (temp < dist[i]) {
ldist[i] = temp;
rdist[i] = 1e6;
} else {
rdist[i] = dist[i];
ldist[i] = 1e6;
}
}
sort(wh, wh+n, cmpl());
int last = m;
for (int i=0; i<n; i++) {
if (ldist[wh[i]] >= 1e6) {
break;
}
int temp = getDistance(last, wh[i]);
if (temp >= ldist[wh[i]]) {
location[wh[i]] = location[m] - ldist[wh[i]];
stype[wh[i]] = 1;
ch[wh[i]] = 1;
last = wh[i];
} else {
location[wh[i]] = location[last] + temp;
stype[wh[i]] = 2;
}
}
sort(wh, wh+n, cmpr());
last = m;
for (int i=0; i<n; i++) {
if (rdist[wh[i]] >= 1e6) {
break;
}
int temp = getDistance(last, wh[i]);
if (temp >= rdist[wh[i]]) {
location[wh[i]] = location[0] + rdist[wh[i]];
stype[wh[i]] = 2;
ch[wh[i]] = 1;
last = wh[i];
} else {
location[wh[i]] = location[last] - temp;
stype[wh[i]] = 1;
}
}
}