Submission #162268

#	Time	Username	Problem	Language	Result	Execution time	Memory
162268		rama_pang	Palembang Bridges (APIO15_bridge)	C++14	22 / 100	67 ms	5072 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() {
    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 = 0, ri = points.size() - 1;
        for (lint j = le; j <= ri; j++) {
            res = min(res, calc(points[i], points[j]));
        }

        // while (le <= ri) {
        //     lint mid = (le + ri) / 2;
        //     if (mid + 1 >= N) {
        //         ri--;
        //         continue;
        //     } else if (mid < 0) {
        //         le++;
        //         continue;
        //     } else {
        //         lint l = get(points[i], points[mid]), r = get(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:57:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (lint i = 0; i < points.size(); i++) {
                      ~~^~~~~~~~~~~~~~~

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