Submission #541590

#	Time	Username	Problem	Language	Result	Execution time	Memory
541590		Deepesson	Wiring (IOI17_wiring)	C++17	100 / 100	92 ms	9920 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;
    int l=0,r=anl.size()-1;
    while(l<r){
        int m = (l+r+1)/2;
        if(anl[m]<=z){
            l=m;
        }else r=m-1;
    }
    best=std::min(best,myabs(anl[l]-z));
    if(l)best=std::min(best,myabs(anl[l-1]-z));
    if(l+1!=anl.size())best=std::min(best,myabs(anl[l+1]-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;
}

Compilation message (stderr)

wiring.cpp: In function 'long long int bestcusto(std::vector<int>&, ll)':
wiring.cpp:20:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     if(l+1!=anl.size())best=std::min(best,myabs(anl[l+1]-z));
      |        ~~~^~~~~~~~~~~~

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