This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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
template <class T> void vec_out(const std::vector<T> &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, std::int64_t, char, std::int64_t>> PSQT(N);
for (auto &[P, S, Q, T] : PSQT) {
std::cin >> P >> S >> Q >> T;
}
std::int64_t ans = 0;
std::vector<std::pair<std::int64_t, std::int64_t>> HW;
for (auto [P, S, Q, T] : PSQT) {
if (P == Q) {
ans += std::abs(T - S);
continue;
}
// the roads
ans++;
HW.emplace_back(S, T);
}
std::sort(HW.begin(), HW.end(), [](const auto &x, const auto &y) {
return (x.first + x.second) < (y.first + y.second);
});
auto calc = [&](std::int64_t S, std::int64_t T, std::int64_t x) {
return std::abs(S - x) + std::abs(T - x) + 1;
};
auto get = [&](int l, int r) {
if (l > r) {
return std::vector<std::int64_t>{};
}
std::vector<std::int64_t> pts;
for (int i = l; i <= r; i++) {
auto &&[H, W] = HW[i];
pts.push_back(H);
pts.push_back(W);
}
std::sort(pts.begin(), pts.end());
return pts;
};
if (K == 1) {
// find median as that is optimal for the
// for all sum abs(S - x) + abs(T - x)
auto pts = get(0, HW.size() - 1);
auto mid = pts.size() / 2;
mid--;
for (auto x : pts) {
ans += std::abs(x - pts[mid]);
}
std::cout << ans << "\n";
return 0;
}
// split at some point i
// then using same median technique as in K = 1
// then we get 2 sub vectors => in each find median (still optimal) and then
// add them up, thus giving you the 2 bridges
std::int64_t res = LLONG_MAX;
for (int f = 0; f < HW.size(); f++) {
// 0 HW.size() - 1
// HW.size() - 1 + 1
auto fir = get(0, f);
auto sec = get(f + 1, HW.size() - 1);
auto m0 = fir.size() / 2;
m0--;
auto m1 = sec.size() / 2;
m1--;
std::int64_t tmp = 0;
for (auto x : fir) {
tmp += std::abs(x - fir[m0]);
}
for (auto x : sec) {
tmp += std::abs(x - sec[m1]);
}
res = std::min(res, tmp);
}
ans += res;
std::cout << ans << "\n";
return 0;
}
Compilation message (stderr)
Palembang_Bridges.cpp: In function 'int main()':
Palembang_Bridges.cpp:93:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
Palembang_Bridges.cpp:48:10: warning: variable 'calc' set but not used [-Wunused-but-set-variable]
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |