Submission #162271

#	Time	Username	Problem	Language	Result	Execution time	Memory
162271		rama_pang	Palembang Bridges (APIO15_bridge)	C++14	22 / 100	2072 ms	4980 KiB

bridge

#include <bits/stdc++.h>
using namespace std;
using lint = long long;

lint K, N;
lint ans;
vector<pair<lint, lint>> A;

inline lint labs(lint x) {
    if (x < 0) return -x;
    return x;
}

lint solve_1() {
    vector<lint> points;

    for (int i = 0; i < N; i++) {
        points.emplace_back(A[i].first);
        points.emplace_back(A[i].second);
    }

    sort(points.begin(), points.end());

    lint res = 0;

    for (int i = 0; i < N; i++) 
        res -= points[i];
    
    for (int i = N; i < N + N; i++)
        res += points[i];
    
    return res;
}

lint solve_2() {
    if (N == 0) 
        return 0;

    auto calc = [&](lint B1, lint B2) {
        lint res = 0;

        for (lint i = 0; i < N; i++) {
            res += min(labs(B1 - A[i].first) + labs(B1 - A[i].second), 
                       labs(B2 - A[i].first) + labs(B2 - A[i].second));
        }

        return (lint)res;
    };

    lint res = INT64_MAX;
    vector<lint> points;

    for (int i = 0; i < N; i++) {
        points.emplace_back(A[i].first);
        points.emplace_back(A[i].second);
    }
    
    sort(points.begin(), points.end());

    for (lint i = 0; i < points.size(); i++) {
        lint le = i, ri = points.size() - 1;

        while (le <= ri) {
            lint mid = (le + ri) / 2;
            if (mid + 1 >= points.size()) {
                ri--;
                continue;
            } else if (mid < 0) {
                le++;
                continue;
            } else {
                lint l = calc(points[i], points[mid]), r = calc(points[i], points[mid + 1]);
                res = min(res, l), res = min(res, r);
                if (l < r) {
                    ri = mid;
                } else {
                    le = mid + 1;
                }
            }
        }

    }

    return res;
}

lint solve() {
    sort(A.begin(), A.end());
    N = A.size();

    if (K == 1)
        return N + solve_1();
    else
        return N + solve_2();
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> K >> N;

    for (int i = 0; i < N; i++) {
        char Z1, Z2;
        lint B1, B2;

        cin >> Z1 >> B1 >> Z2 >> B2;
        if (B1 > B2) swap(B1, B2);

        if (Z1 == Z2)
            ans += B2 - B1;
        else
            A.emplace_back(B1, B2);
    }

    ans += solve();

    cout << ans << "\n";

    return 0;
}

Compilation message (stderr)

bridge.cpp: In function 'lint solve_2()':
bridge.cpp:60:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (lint i = 0; i < points.size(); i++) {
                      ~~^~~~~~~~~~~~~~~
bridge.cpp:65:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (mid + 1 >= points.size()) {
                 ~~~~~~~~^~~~~~~~~~~~~~~~

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