Submission #958335

#	Time	Username	Problem	Language	Result	Execution time	Memory
958335		riariti	Palembang Bridges (APIO15_bridge)	C++17	22 / 100	39 ms	8148 KiB

bridge

#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++) {
        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;
}

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:110:14: warning: unused variable 'md0' [-Wunused-variable]
Palembang_Bridges.cpp:111:14: warning: unused variable 'md1' [-Wunused-variable]
Palembang_Bridges.cpp:48:10: warning: variable 'calc' set but not used [-Wunused-but-set-variable]
Palembang_Bridges.cpp: In instantiation of 'void vec_out(const std::vector<_Tp>&) [with T = long int]':
Palembang_Bridges.cpp:101:20:   required from here
Palembang_Bridges.cpp:14:15: warning: unused variable 'x' [-Wunused-variable]

• Subtask 1: 8 / 8
• Subtask 2: 14 / 14
• Subtask 3: 0 / 9
• Subtask 4: 0 / 32
• Subtask 5: 0 / 37