Submission #1130526

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130526		AnhPham	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	269 ms	13752 KiB

bridge

#include <bits/stdc++.h>

using namespace std;

#define int     long long
#define sz(v)   (int)(v).size()
#define all(v)  (v).begin(), (v).end()

const   int     MOD = (int)1e9 + 7;
const   int     INF = (int)1e18 + 18;

void solve();

int32_t main() {
#define CODE1 "task"
    if (fopen(CODE1".inp", "r"))
        freopen(CODE1".inp", "r", stdin), freopen(CODE1".out", "w", stdout);

#define CODE2 ""
    if (fopen(CODE2".inp", "r"))
        freopen(CODE2".inp", "r", stdin), freopen(CODE2".out", "w", stdout);

    cin.tie(nullptr), cout.tie(nullptr) -> sync_with_stdio(false);
    int testcases = 1;

#define multitest 0
    if (multitest) { cin >> testcases; } for (; testcases--;) { solve(); }
}

/** [Pham Hung Anh - 12I - Tran Hung Dao High School for Gifted Student] **/
/**                            The Last Dance                            **/

const int mxN = 1e5 + 5;

int K, N;
int same_side;
vector <int> buildings;
vector <pair <int, int>> opposite;

namespace sub12 { // O(N)
    bool check_condition() {
        return K == 1;
    }

    void solve() {
        if (sz(buildings) == 0)
            return void(cout << same_side << '\n');

        int ans = same_side;
        int m = sz(buildings);
        int median = buildings[(m + 1) / 2];
        for (int i = 0; i < m; ++i)
            ans += abs(median - buildings[i]);
        
        cout << ans + sz(buildings) / 2 << '\n';
    }
}

namespace sub3 { // O(N^3)
    bool check_condition() {
        return N <= 100;
    }

    void solve() {
        if (sz(buildings) == 0)
            return void(cout << same_side << '\n');

        int ret = INF;
        for (int i = 0; i < sz(buildings); ++i)
            for (int j = i + 1; j < sz(buildings); ++j) {
                int bridge1 = buildings[i], bridge2 = buildings[j];
                int sum = 0;
                for (auto p : opposite)
                    sum += min(abs(p.first - bridge1) + abs(p.second - bridge1), abs(p.first - bridge2) + abs(p.second - bridge2)) + 1;
                
                ret = min(ret, sum);
            }
            
        cout << ret + same_side << '\n';
    }
}

namespace sub4 { // O(log3(N)^2 * N)
    bool check_condition() {
        return N <= 1000;
    }

    int get(int bridge1, int bridge2) {
        int sum = same_side;
        for (auto p : opposite)
            sum += min(abs(p.first - bridge1) + abs(p.second - bridge1), abs(p.first - bridge2) + abs(p.second - bridge2)) + 1;
        
        return sum;
    }

    int ternary_search(int bridge1) {
        int ret = INF;
        int lo = bridge1 + 1, hi = sz(buildings) - 1;
        while (lo <= hi) {
            int mid1 = lo + (hi - lo) / 3;
            int mid2 = hi - (hi - lo) / 3;

            int sum1 = get(buildings[bridge1], buildings[mid1]);
            int sum2 = get(buildings[bridge1], buildings[mid2]);
            ret = min(ret, min(sum1, sum2));

            if (sum1 < sum2)
                hi = mid2 - 1;
            else if (sum1 > sum2)
                lo = mid1 + 1;
            else
                lo = mid1 + 1, hi = mid2 - 1;
        }

        return ret;
    }

    void solve() {
        int ans = INF;
        int lo = 0, hi = sz(buildings) - 2;
        while (lo <= hi) {
            int mid1 = lo + (hi - lo) / 3;
            int mid2 = hi - (hi - lo) / 3;
            
            int ans1 = ternary_search(mid1);
            int ans2 = ternary_search(mid2);
            ans = min(ans, min(ans1, ans2));

            if (ans1 < ans2)
                hi = mid2 - 1;
            else if (ans1 > ans2)
                lo = mid1 + 1;
            else
                lo = mid1 + 1, hi = mid2 - 1;
        }

        cout << ans << '\n';
    }
}

namespace sub5 {
    int suml = 0, sumr = 0;
    multiset <int> lo, hi;
    
    void balance() {
        while (sz(lo) > sz(hi)) {
            int x = *lo.rbegin();
            hi.emplace(x);
            suml -= x;
            sumr += x;
            lo.erase(lo.find(x));
        }
    
    
        while (sz(hi) > sz(lo)) {
            int x = *hi.begin();
            lo.emplace(x);
            suml += x;
            sumr -= x;
            hi.erase(hi.find(x));
        }
    }
    
    void add(int x) {
        lo.emplace(x);
        suml += x;
    
        balance();
    }
    
    void solve() {
        sort(opposite.begin(), opposite.end(), [&](pair <int, int> opposite, pair <int, int> b) -> bool {
            return opposite.first + opposite.second < b.first + b.second;
        });
    
        vector <int> pref(sz(opposite) + 1);
        for(int i = 0; i < sz(opposite); ++i) {
            add(opposite[i].first);
            add(opposite[i].second);
    
            pref[i + 1] = sumr - suml;
        }
    
        int ans = pref[sz(opposite)];
    
        lo.clear();
        hi.clear();
        suml = sumr = 0;

        for(int i = sz(opposite) - 1; i >= 0; --i) {
            add(opposite[i].first);
            add(opposite[i].second);

            ans = min(ans, pref[i] + sumr - suml);
        }
    
        cout << ans + sz(opposite) + same_side << '\n';
    }
}

void solve() {
    cin >> K >> N;

    for (int i = 1; i <= N; ++i) {
        char p, q; int s, t; cin >> p >> s >> q >> t;

        if (p == q)
            same_side += abs(s - t);
        else
            buildings.push_back(s), buildings.push_back(t), 
            opposite.emplace_back(min(s, t), max(s, t));
    }

    sort(all(buildings));

    if (sub12 :: check_condition())
        sub12 :: solve();
    else if (sub3 :: check_condition())
        sub3 :: solve();
    else if (sub4 :: check_condition())
        sub4 :: solve();
    else
        sub5 :: solve();
}

Compilation message (stderr)

bridge.cpp: In function 'int32_t main()':
bridge.cpp:17:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |         freopen(CODE1".inp", "r", stdin), freopen(CODE1".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
bridge.cpp:17:50: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |         freopen(CODE1".inp", "r", stdin), freopen(CODE1".out", "w", stdout);
      |                                           ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
bridge.cpp:21:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         freopen(CODE2".inp", "r", stdin), freopen(CODE2".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
bridge.cpp:21:50: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         freopen(CODE2".inp", "r", stdin), freopen(CODE2".out", "w", stdout);
      |                                           ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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