Submission #373176

#	Time	Username	Problem	Language	Result	Execution time	Memory
373176		Doxeno	Wiring (IOI17_wiring)	C++17	0 / 100	1 ms	364 KiB

wiring

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
using namespace std;
typedef long long ll;

ll min_total_length(vector<int> r, vector<int> b){
    int N = r.size(), M = b.size();
    int ind = 0;
    set<int> rs[N], bs[M];
    for(int i = 0; i < N; i++){
        while(ind < M-1 && b[ind] < r[i])ind++;
        if(ind == 0){rs[i].insert(0); bs[0].insert(i);}
        else{
            if(abs(b[ind] - r[i]) <= abs(b[ind-1] - r[i])){rs[i].insert(ind); bs[ind].insert(i);}
            if(abs(b[ind] - r[i]) >= abs(b[ind-1] - r[i])){rs[i].insert(ind-1); bs[ind-1].insert(i);}
        }
    }
    ind = 0;
    for(int i = 0; i < M; i++){
        while(ind < N-1 && r[ind] < b[i])ind++;
        if(ind == 0){bs[i].insert(0); rs[0].insert(i);}
        else {
            if(abs(r[ind] - b[i]) <= abs(r[ind-1] - b[i])){bs[i].insert(ind); rs[ind].insert(i);}
            if(abs(r[ind] - b[i]) >= abs(r[ind-1] - b[i])){bs[i].insert(ind-1); rs[ind-1].insert(i);}
        }
    }
    int ri = 0, bi = 0;
    for(int kekw = 0; kekw < M+N; kekw++){
        if(bi >= M || ri < N && r[ri] < b[bi]){
            vector<int> k;
            for(auto x: rs[ri]){
                if(k.size() < rs[ri].size()-1 && bs[x].size() > 1){
                    k.pb(x);
                }
            }
            for(auto x: k){rs[ri].erase(x); bs[x].erase(ri);}
            ri++;
        }else{
            vector<int> k;
            for(auto x: bs[bi]){
                if(k.size() < bs[bi].size()-1 && rs[-x].size() > 1){
                    k.pb(x);
                }
            }
            for(auto x: k){bs[bi].erase(x); rs[x].erase(bi);}

            bi++;
        }
    }
    ll ans = 0;
    for(int i = 0; i < N; i++){
        for(auto x: rs[i])ans += abs(r[i]-b[x]);
    }
    return ans;
}

Compilation message (stderr)

wiring.cpp: In function 'll min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:31:30: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   31 |         if(bi >= M || ri < N && r[ri] < b[bi]){

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