Submission #583884

#	Time	Username	Problem	Language	Result	Execution time	Memory
583884		MohamedFaresNebili	Wiring (IOI17_wiring)	C++14	0 / 100	413 ms	262144 KiB

wiring

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

        using namespace std;
        using namespace __gnu_pbds;

        using ll = long long;
        using pi = pair<ll, pair<ll, ll>>;
        using ii = pair<ll, ll>;

        #define pb push_back
        #define pp pop_back
        #define ff first
        #define ss second
        #define lb lower_bound

        typedef tree<int, null_type, less<int>, rb_tree_tag,
            tree_order_statistics_node_update> indexed_set;

        ll min_total_length(vector<int> r, vector<int> b) {
            vector<ll> R, B;
            for(auto u : r) R.pb(u);
            for(auto u : b) B.pb(u);
            ll N = R.size(), M = B.size(), res = 0;
            vector<bool> vis(N, 0), seen(M, 0);
            priority_queue<pi, vector<pi>, greater<pi>> pq;
            for(ll l = 0; l < N; l++) {
                for(ll i = 0; i < M; i++) {
                    pq.push({abs(R[l] - B[i]), {l, i}});
                }
            }
            while(!pq.empty()) {
                ll u = pq.top().ss.ff, v = pq.top().ss.ss, k = pq.top().ff; pq.pop();
                if(vis[u] || seen[v]) continue;
                res += k; vis[u] = seen[v] = 1;
            }
            for(ll l = 0; l < N; l++) {
                if(vis[l]) continue;
                auto it = lb(B.begin(), B.end(), R[l]);
                ll ans = 1e18 + 7;
                if(it != B.end()) ans = min(ans, abs(*it - R[l]));
                if(it != B.begin()) {
                    it--; ans = min(ans, abs(*it - R[l]));
                }
                res += ans;
            }
            for(ll l = 0; l < M; l++) {
                if(seen[l]) continue;
                auto it = lb(R.begin(), R.end(), B[l]);
                ll ans = 1e18 + 7;
                if(it != R.end()) ans = min(ans, abs(*it - B[l]));
                if(it != R.begin()) {
                    it--; ans = min(ans, abs(*it - B[l]));
                }
                res += ans;
            }
            return res;
        }

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