| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 413194 | KoD | 철로 (IOI14_rail) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "rail.h"
template <class T>
using Vec = std::vector<T>;
int dist(const int i, const int j) {
if (i == j) return 0;
if (i > j) return dist(j, i);
static std::map<std::pair<int, int>, int> memo;
auto& val = memo[{i, j}];
if (val == 0) {
val = getDistance(i, j);
}
return val;
}
void findLocation(int n, int first, int location[], int stype[]) {
location[0] = first;
stype[0] = 1;
Vec<std::pair<int, int>> order;
order.reserve(n - 1);
for (int i = 1; i < n; ++i) {
order.emplace_back(dist(0, i), i);
}
std::sort(order.begin(), order.end());
int l = 0, r = order[0].second;
location[r] = location[l] + order[0].first;
stype[r] = 2;
order.erase(order.begin());
std::map<int, int> idx;
idx[location[l]] = l;
idx[location[r]] = r;
for (const auto [d_0, i]: order) {
const auto d_l = dist(l, i);
const auto d_r = dist(r, i);
const auto m = ((location[l] + d_l) + (location[r] - d_r)) / 2;
if ((idx.find(m) == idx.end() and m > first) or (id.find(m) != idx.end() and stype[idx[m]] == 1)) {
location[i] = location[l] + d_l;
stype[i] = 2;
if (location[r] < location[i]) {
r = i;
}
}
else {
location[i] = location[r] - d_r;
stype[i] = 1;
if (location[i] < location[l]) {
l = i;
}
}
idx[location[i]] = i;
}
}