이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#line 1 "Palembang_Bridges.cpp"
#include <bits/stdc++.h>
#define int std::int64_t
#ifdef local
#define dbg(__VA_ARGS__) \
std::cerr << "[DBG|" << __LINE__ << "]: " << __VA_ARGS__ << std::endl;
#define cerr(__VA_ARGS__) std::cerr << __VA_ARGS__;
template <class T> void vec_out(const std::vector<T> &cc) {
dbg("vector: ");
for (auto x : cc) {
cerr(x << " ");
}
cerr("\n");
}
#else
#define dbg(...)
#define cerr(...)
template <class T> void vec_out(const std::vector<T> &cc) {}
#endif
std::int32_t 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 (S > T) {
std::swap(S, T);
}
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++) {
auto fir = get(0, f);
auto sec = get(f + 1, HW.size() - 1);
if (fir.empty() || sec.empty()) {
continue;
}
vec_out(fir);
vec_out(sec);
auto m0 = fir.size() / 2;
m0--;
auto m1 = sec.size() / 2;
m1--;
auto md0 = fir[m0];
auto md1 = fir[m1];
std::int64_t tmp = 0;
// for (auto [H, W] : HW) {
// tmp += std::min(calc(H, W, md0), calc(H, W, md1));
// }
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;
}
컴파일 시 표준 에러 (stderr) 메시지
Palembang_Bridges.cpp: In function 'int32_t main()':
Palembang_Bridges.cpp:101:23: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<std::pair<long int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
Palembang_Bridges.cpp:118:14: warning: unused variable 'md0' [-Wunused-variable]
Palembang_Bridges.cpp:119:14: warning: unused variable 'md1' [-Wunused-variable]
Palembang_Bridges.cpp:56: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... |