| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 128613 | antimirage | 철로 (IOI14_rail) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "rail.h"
#include "grader.cpp"
#include <bits/stdc++.h>
#define fr first
#define sc second
#define mk make_pair
#define pb push_back
#define all(s) s.begin(), s.end()
using namespace std;
const int N = 5005;
int dist[2][N];
vector <int> lft, rght;
bool cmp1 (int a, int b) {
return dist[0][a] < dist[0][b];
}
bool cmp2 (int a, int b) {
return dist[1][a] < dist[1][b];
}
void findLocation(int n, int pos, int a[], int t[])
{
int mn = 1e9 + 7, ind, asd;
a[0] = pos, t[0] = 1;
if (n == 1) return;
for (int i = 1; i < n; i++) {
dist[0][i] = getDistance(0, i);
if (dist[0][i] < mn) {
mn = dist[0][i];
ind = i;
}
}
a[ind] = pos + mn; t[ind] = 2;
mn = 1e9 + 7;
for (int i = 0; i < n; i++) {
if (i == ind) continue;
dist[1][i] = getDistance(ind, i);
if (dist[1][i] < mn) {
mn = dist[1][i];
asd = i;
}
}
a[asd] = a[ind] - mn; t[asd] = 1;
for (int i = 0; i < n; i++) {
if (i == asd || i == ind) continue;
dist[0][i] = getDistance(asd, i);
}
for (int i = 0; i < n; i++) {
if (i == ind || i == asd) continue;
if (dist[0][i] < dist[1][i]) {
rght.pb(i);
}
else if (dist[0][i] > dist[1][i]) {
lft.pb(i);
}
}
sort(all(rght), cmp1);
sort(all(lft), cmp2);
int lastd = -1, lastc = 0;
for (int i = 0; i < (int)rght.size(); i++) {
int it = rght[i];
if (lastd == -1) {
lastd = it;
a[it] = a[asd] + dist[0][it];
t[it] = 2;
}
else {
int res = getDistance(lastd, it), nxt = a[asd] + dist[0][it];
int ok = a[lastd] - res;
for (int j = 0; j < i; j++) {
if (t[rght[j]] == 2 && a[rght[j]] > ok && a[rght[j]] - ok + dist[0][j] == dist[0][it] )
assert(0);
}
if (nxt < 1000000 && res == 2 * (a[lastd] - a[lastc]) + nxt - a[lastd]) {
a[it] = nxt, lastd = it; t[it] = 2;
}
else {
a[it] = a[lastd] - res; t[it] = 1;
if (a[lastc] < a[it])
lastc = it;
}
}
}
lastc = -1, lastd = ind;
pos = a[ind];
for (int i = 0; i < (int)lft.size(); i++) {
int it = lft[i];
if (lastc == -1) {
lastc = it;
a[it] = pos - dist[1][it];
t[it] = 1;
}
else {
int res = getDistance(lastc, it), nxt = a[ind] - dist[1][it];
int ok = a[lastc] + res;
for (int j = 0; j < i; j++) {
if (t[lft[j]] == 1 && a[lft[j]] < ok && ok - a[lft[j]] + dist[1][j] == dist[1][it] )
assert(0);
}
if (nxt >= 0 && res == 2 * (a[lastd] - a[lastc]) + a[lastc] - nxt) {
a[it] = nxt, lastc = it; t[it] = 1;
}
else {
a[it] = a[lastc] + res; t[it] = 2;
if (a[lastd] > a[it])
lastd = it;
}
}
}
}