| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 958196 | riariti | Palembang Bridges (APIO15_bridge) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#line 1 "Palembang_Bridges.cpp"
#include <bits/stdc++.h>
#ifdef local
#define dbg(__VA_ARGS__) \
std::cerr << "[DBG|" << __LINE__ << "]: " << __VA_ARGS__ << std::endl;
#define cerr(__VA_ARGS__) std::cerr << __VA_ARGS__;
#else
#define dbg(...)
#define cerr(...)
#endif
const auto vec_out = [](const std::vector<int> &cc) {
dbg("vector: ");
for (auto x : cc) {
cerr(x << " ");
}
cerr("\n");
};
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int K, N;
std::cin >> K >> N;
std::vector<std::tuple<char, int, char, int>> PSQT(N);
for (auto &[P, S, Q, T] : PSQT) {
std::cin >> P >> S >> Q >> T;
}
// std::vector<int> cc;
// for (auto [P, S, Q, T] : PSQT) {
// cc.push_back(S);
// cc.push_back(T);
// }
// std::ranges::sort(cc);
// cc.erase(std::unique(cc.begin(), cc.end()), cc.end());
// vec_out(cc);
// auto compress = [cc](int v) {
// return std::distance(cc.begin(), std::ranges::lower_bound(cc, v));
// };
// auto expand = [cc](int v) { return cc[v]; };
// for (auto &[P, S, Q, T] : PSQT) {
// S = compress(S);
// T = compress(T);
// }
// dbg("Compressed here");
// for (auto [P, S, Q, T] : PSQT) {
// dbg(P << " " << S << " " << Q << " " << T);
// }
// median => at max 4 possibilites, then sliding window all throughout
// optimal to keep one of the points at someones house or office tho
std::vector<int> pos;
for (auto [P, S, Q, T] : PSQT) {
pos.push_back(S);
pos.push_back(T);
}
vec_out(pos);
// K = 1 minimized at median since sum is as follows:
//
// sum of all |Si - x| + |Ti - x|
auto m = std::midpoint<int>(0, pos.size());
std::nth_element(pos.begin(), pos.begin() + m, pos.end());
vec_out(pos);
auto med = pos[m];
std::int64_t ans = 0;
for (auto [P, S, Q, T] : PSQT) {
ans += static_cast<std::int64_t>(std::abs(S - med)) + std::abs(T - med);
}
std::cout << ans << "\n";
return 0;
}