Submission #958341

#	Time	Username	Problem	Language	Result	Execution time	Memory
958341		riariti	Palembang Bridges (APIO15_bridge)	C++17	63 / 100	2084 ms	7492 KiB

bridge

#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

using namespace std;

using ll = long long;

const int mod = ll(1e9) + 7; //(b + (a%b)) % b (to mod -1%(10^9+7) correctly in
                             // c++ its -1 but its suppose to be 10^9+6
const int N = ll(2e5) + 100;
const long long inf = 5e18;

int k, n, m;
pair<int, int> point[N];

#define ff first
#define ss second
bool cmp(pair<int, int> a, pair<int, int> b) {
    return (a.ff + a.ss) < (b.ff + b.ss);
}

#define all(a) a.begin(), a.end()
#define pb push_back

vector<int> get(int l, int r) {
    if (l > r)
        return {};
    vector<int> res;
    for (int i = l; i <= r; i++)
        res.pb(point[i].ff), res.pb(point[i].ss);
    sort(all(res));
    return res;
}

std::int32_t main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    cin >> k >> n;
    long long ex = 0;
    for (int i = 1; i <= n; i++) {
        char p, q;
        int s, t;
        cin >> p >> s >> q >> t;
        if (s > t)
            swap(s, t);
        if (p == q)
            ex += t - s;
        else {
            ex++;
            point[++m] = {s, t};
        }
    }
    sort(point + 1, point + m + 1, cmp);
    long long ans = 0;
    if (k == 1) {
        vector<int> pos = get(1, m);
        int mid = (pos.size()) / 2;
        for (auto x : pos)
            ans += abs(pos[mid] - x);
    } else if (k == 2 && m) {
        ans = inf;
        for (int i = 1; i <= m; i++) {
            vector<int> pos1 = get(1, i), pos2 = get(i + 1, m);
            int mid1 = (pos1.size()) / 2, mid2 = (pos2.size()) / 2;
            long long res = 0;
            for (auto x : pos1)
                res += abs(pos1[mid1] - x);
            for (auto x : pos2)
                res += abs(pos2[mid2] - x);
            ans = min(ans, res);
        }
    }
    cout << ans + ex;

    /*
    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;
}

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