# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
236205 | Bilyana | 철로 (IOI14_rail) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}
}
}