| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 413194 | KoD | 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 "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;
}
}