Submission #541589

#	Time	Username	Problem	Language	Result	Execution time	Memory
541589		Deepesson	Wiring (IOI17_wiring)	C++17	7 / 100	1087 ms	4172 KiB

wiring

#include <bits/stdc++.h>
#include "wiring.h"
using ll = long long;
ll myabs(ll x){
    if(x<0)return x*(-1);
    return x;
}
typedef std::pair<ll,ll> pll;
long long bestcusto(std::vector<int> anl,ll z){
    ll best=1e9;
    for(auto&x:anl){
        best=std::min(best,myabs(x-z));
    }
    return best;
}
long long min_total_length(std::vector<int> r, std::vector<int> b) {
    ll ans=0;
    for(auto&x:r)ans+=bestcusto(b,x);
    for(auto&x:b)ans+=bestcusto(r,x);
    std::priority_queue<ll,std::vector<ll>,std::greater<ll>> abrer,abreb;
    std::vector<pll> vec;
    for(auto&x:r)vec.push_back({x,0});
    for(auto&x:b)vec.push_back({x,1});
    std::sort(vec.begin(),vec.end());
    for(auto&x:vec){
        ll cor=x.second;
        ll pos=x.first;
        if(!cor){///Vermelho
            ll custo = bestcusto(b,pos);
            ll delta = pos-custo;
            ll melhor = 1e9;
            if(abreb.size()){
                melhor=abreb.top();
            }
            if(melhor+delta<0){
                long long ganha = melhor+delta;
                ans+=ganha;
                abreb.pop();
                abrer.push(-pos-custo-ganha);
            }else abrer.push(-pos-custo);
        }else {///Azul
            ll custo = bestcusto(r,pos);
            ll delta = pos-custo;
            ll melhor = 1e9;
            if(abrer.size()){
                melhor=abrer.top();
            }
            if(melhor+delta<0){
                long long ganha = melhor+delta;
                ans+=ganha;
                abrer.pop();
                abreb.push(-pos-custo-ganha);
            }else abreb.push(-pos-custo);
        }
    }
    return ans;
}

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