Submission #1064160

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064160		TheQuantiX	Wiring (IOI17_wiring)	C++17	0 / 100	266 ms	30848 KiB

wiring

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

constexpr ll INF = 1000000000000000000LL;

ll n, m, q, k, x, y, a, c;

long long min_total_length(std::vector<int> r, std::vector<int> b) {
    n = r.size();
    m = b.size();
    vector< pair<ll, ll> > vec;
    for (int i : r) {
        vec.push_back({i, 1});
    }
    for (int i : b) {
        vec.push_back({i, 2});
    }
    sort(vec.begin(), vec.end());
    set<ll> st;
    for (int i = 0; i < n + m; i++) {
        if (i != 0 && vec[i].second != vec[i - 1].second) {
            st.insert(vec[i].first);
        }
        if (i != n + m - 1 && vec[i].second != vec[i + 1].second) {
            st.insert(vec[i].first);
        }
    }
    set< pair<ll, pair<ll, ll> > > two, one;
    vector<bool> used1(n), used2(m);
    for (int i = 0; i < n; i++) {
        if (st.count(r[i])) {
            continue;
        }
        if (r[i] <= b[b.size() - 1]) {
            ll x = lower_bound(b.begin(), b.end(), r[i]) - b.begin();
            two.insert({abs(r[i] - b[x]), {i, x}});
        }
        if (r[i] >= b[0]) {
            ll x = (--upper_bound(b.begin(), b.end(), r[i])) - b.begin();
            two.insert({abs(r[i] - b[x]), {i, x}});
        }
    }
    for (int i = 0; i < m; i++) {
        if (st.count(b[i])) {
            continue;
        }
        if (b[i] <= r[r.size() - 1]) {
            ll x = lower_bound(r.begin(), r.end(), b[i]) - r.begin();
            two.insert({abs(r[x] - b[i]), {x, i}});
        }
        if (b[i] >= r[0]) {
            ll x = (--upper_bound(r.begin(), r.end(), b[i])) - r.begin();
            two.insert({abs(r[x] - b[i]), {x, i}});
        }
    }
    // for (auto i : two) {
    //     cout << i.first << ' ' << i.second.first << ' ' << i.second.second << '\n';
    // }
    // cout << '\n';
    ll ans = 0;
    while (two.size() > 0 || one.size() > 0) {
        pair<ll, ll> p1 = {-1, -1}, p2 = {-1, -1};
        while (!two.empty() && p2.first == -1) {
            p2 = (*two.begin()).second;
            two.erase({abs(r[p2.first] - b[p2.second]), p2});
            if (used1[p2.first] && used2[p2.second]) {
                p2 = {-1, -1};
                continue;
            }
            if (used1[p2.first] || used2[p2.second]) {
                one.insert({abs(r[p2.first] - b[p2.second]), p2});
                p2 = {-1, -1};
                continue;
            }
            break;
        }
        while (!one.empty() && p1.first == -1) {
            p1 = (*one.begin()).second;
            one.erase({abs(r[p1.first] - b[p1.second]), p1});
            if (used1[p1.first] && used2[p1.second]) {
                p1 = {-1, -1};
                continue;
            }
            break;
        }
        if (p1.first == -1 && p2.first == -1) {
            break;
        }
        // cout << p1.first << ' ' << p1.second << '\n';
        // cout << p2.first << ' ' << p2.second << '\n';
        ll a1 = (p1.first == -1 ? INF : abs(r[p1.first] - b[p1.second]));
        a1 *= 2;
        ll a2 = (p2.first == -1 ? INF : abs(r[p2.first] - b[p2.second]));
        // cout << min(a1 / 2, a2) << '\n';
        // cout << '\n';
        if (a2 <= a1) {
            ans += a2;
            used1[p2.first] = 1;
            used2[p2.second] = 1;
        }
        else {
            ans += a1 / 2;
            used1[p1.first] = 1;
            used2[p1.second] = 1;
        }
    }
    // for (int i = 0; i < n; i++) {
    //     cout << used1[i] << ' ';
    // }
    // cout << '\n';
    // for (int i = 0; i < m; i++) {
    //     cout << used2[i] << ' ';
    // }
    // cout << '\n';
    for (int i = 0; i < n; i++) {
        if (r[i] <= b[b.size() - 1]) {
            ll x = lower_bound(b.begin(), b.end(), r[i]) - b.begin();
            if (!used1[i] && !used2[x]) {
                two.insert({abs(r[i] - b[x]), {i, x}});
            }
            else if (!used1[i] || !used2[x]) {
                one.insert({abs(r[i] - b[x]), {i, x}});
            }
        }
        if (r[i] >= b[0]) {
            ll x = (--upper_bound(b.begin(), b.end(), r[i])) - b.begin();
            if (!used1[i] && !used2[x]) {
                two.insert({abs(r[i] - b[x]), {i, x}});
            }
            else if (!used1[i] || !used2[x]) {
                one.insert({abs(r[i] - b[x]), {i, x}});
            }
        }
    }
    for (int i = 0; i < m; i++) {
        if (b[i] <= r[r.size() - 1]) {
            ll x = lower_bound(r.begin(), r.end(), b[i]) - r.begin();
            if (!used1[x] && !used2[i]) {
                two.insert({abs(r[x] - b[i]), {x, i}});
            }
            else if (!used1[x] || !used2[i]) {
                one.insert({abs(r[x] - b[i]), {x, i}});
            }
        }
        if (b[i] >= r[0]) {
            ll x = (--upper_bound(r.begin(), r.end(), b[i])) - r.begin();
            if (!used1[x] && !used2[i]) {
                two.insert({abs(r[x] - b[i]), {x, i}});
            }
            else if (!used1[x] || !used2[i]) {
                one.insert({abs(r[x] - b[i]), {x, i}});
            }
        }
    }
    // for (auto i : two) {
    //     cout << i.first << ' ' << i.second.first << ' ' << i.second.second << '\n';
    // }
    // cout << '\n';
    while (two.size() > 0 || one.size() > 0) {
        // for (int i = 0; i < n; i++) {
        //     cout << used1[i] << ' ';
        // }
        // cout << '\n';
        // for (int i = 0; i < m; i++) {
        //     cout << used2[i] << ' ';
        // }
        // cout << '\n';
        // cout << '\n';
        pair<ll, ll> p1 = {-1, -1}, p2 = {-1, -1};
        while (!two.empty() && p2.first == -1) {
            p2 = (*two.begin()).second;
            two.erase({abs(r[p2.first] - b[p2.second]), p2});
            if (used1[p2.first] && used2[p2.second]) {
                p2 = {-1, -1};
                continue;
            }
            if (used1[p2.first] || used2[p2.second]) {
                one.insert({abs(r[p2.first] - b[p2.second]), p2});
                p2 = {-1, -1};
                continue;
            }
            break;
        }
        while (!one.empty() && p1.first == -1) {
            p1 = (*one.begin()).second;
            one.erase({abs(r[p1.first] - b[p1.second]), p1});
            if (used1[p1.first] && used2[p1.second]) {
                p1 = {-1, -1};
                continue;
            }
            break;
        }
        if (p1.first == -1 && p2.first == -1) {
            break;
        }
        // cout << p1.first << ' ' << p1.second << '\n';
        // cout << p2.first << ' ' << p2.second << '\n';
        ll a1 = (p1.first == -1 ? INF : abs(r[p1.first] - b[p1.second]));
        a1 *= 2;
        ll a2 = (p2.first == -1 ? INF : abs(r[p2.first] - b[p2.second]));
        // cout << min(a1 / 2, a2) << '\n';
        // cout << '\n';
        if (a2 <= a1) {
            ans += a2;
            used1[p2.first] = 1;
            used2[p2.second] = 1;
            if (p1.first != -1) {
                one.insert({a1 / 2, p1});
            }
        }
        else {
            ans += a1 / 2;
            used1[p1.first] = 1;
            used2[p1.second] = 1;
            if (p2.first != -1) {
                two.insert({a2, p2});
            }
        }
    }
    return ans;
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 13
• Subtask 3: 0 / 10
• Subtask 4: 0 / 25
• Subtask 5: 0 / 45