제출 #540286

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
540286		Deepesson	전선 연결 (IOI17_wiring)	C++17	0 / 100	1096 ms	6168 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 variacao={};
    std::vector<pll> alteracoes;
    for(auto&x:r)alteracoes.push_back({x,1});
    for(auto&x:b)alteracoes.push_back({x,-1});
    std::sort(alteracoes.begin(),alteracoes.end());
    std::vector<ll> abreb,abrer,fechab,fechar;
    ll resp=0;
    for(auto&x:alteracoes){
        ll cor = x.second,pos=x.first;
        if(cor==1){
            if(resp<0){
                fechar.push_back(pos);
            }else abrer.push_back(pos);
            resp++;
        }else {
            if(resp<=0){
                abreb.push_back(pos);
            }else fechab.push_back(pos);
            resp--;
        }
    }
    ll ans=0;
    std::sort(abreb.begin(),abreb.end());
    std::sort(abrer.begin(),abrer.end());
    std::sort(fechab.begin(),fechab.end());
    std::sort(fechar.begin(),fechar.end());

    {
        std::vector<pll> penalidades;
        ll dif = myabs(r.size()-b.size());
        if(resp>0){///Quantidade maior de vermelhos
            assert(abrer.size()>fechab.size());
          ///  std::cout<<abrer.size()<<" "<<fechab.size()<<":\n";
            for(auto&x:abrer){
                penalidades.push_back({bestcusto(b,x)-x,x});
            }
            std::sort(penalidades.begin(),penalidades.end());
           /// std::cout<<dif<<" "<<penalidades.size()<<"<-\n";
            for(int i=0;i<dif;++i){
                ans+=bestcusto(b,penalidades[i].second);
               /// std::cout<<"Remove "<<penalidades[i].second<<" "<< bestcusto(b,penalidades[i].second)<<" "<<ans<<"\n";
            }
            abrer.clear();
            for(int i=dif;i<penalidades.size();++i){
                abrer.push_back(penalidades[i].second);
            }
           /// std::cout<<"Nov: "<<abreb.size()<<" "<<penalidades.size()<<"\n";
        }else if(resp<0){
            assert(abreb.size()>fechar.size());
         ///   std::cout<<abreb.size()<<" "<<fechar.size()<<":\n";
            for(auto&x:abreb){
                penalidades.push_back({bestcusto(r,x)-x,x});
            }
            std::sort(penalidades.begin(),penalidades.end());
           /// std::cout<<dif<<" "<<penalidades.size()<<"<-\n";
            for(int i=0;i<dif;++i){
                ans+=bestcusto(r,penalidades[i].second);
              ///  std::cout<<"Remove "<<penalidades[i].second<<" "<< bestcusto(r,penalidades[i].second)<<" "<<ans<<"\n";
            }
            abreb.clear();
            for(int i=dif;i<penalidades.size();++i){
                abreb.push_back(penalidades[i].second);
            }
          ///  std::cout<<"Nov: "<<abreb.size()<<" "<<penalidades.size()<<"\n";
        }
    }
   /// std::cout<<ans<<"!\n";
    std::sort(abreb.begin(),abreb.end());
    std::sort(abrer.begin(),abrer.end());
    std::sort(fechab.begin(),fechab.end());
    std::sort(fechar.begin(),fechar.end());
    ///Abre B com Fecha R
    {
       /// std::cout<<abreb.size()<<" "<<fechar.size()<<"\n";
        ll somab=0,somar=0;
        for(auto&x:abreb)somab+=x;
        for(auto&x:fechar)somar+=x;
        ll dif = myabs(abreb.size()-fechar.size());
        ans+=somar-somab;
    }
    ///Abre R com Fecha B
    {
       /// std::cout<<abrer.size()<<" "<<fechab.size()<<"\n";
        ll somab=0,somar=0;
        for(auto&x:fechab)somab+=x;
        for(auto&x:abrer)somar+=x;
        ll dif = myabs(abrer.size()-fechab.size());
        ans+=somab-somar;
    }
    return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:60:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |             for(int i=dif;i<penalidades.size();++i){
      |                           ~^~~~~~~~~~~~~~~~~~~
wiring.cpp:77:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |             for(int i=dif;i<penalidades.size();++i){
      |                           ~^~~~~~~~~~~~~~~~~~~
wiring.cpp:94:12: warning: unused variable 'dif' [-Wunused-variable]
   94 |         ll dif = myabs(abreb.size()-fechar.size());
      |            ^~~
wiring.cpp:103:12: warning: unused variable 'dif' [-Wunused-variable]
  103 |         ll dif = myabs(abrer.size()-fechab.size());
      |            ^~~
wiring.cpp:17:8: warning: unused variable 'variacao' [-Wunused-variable]
   17 |     ll variacao={};
      |        ^~~~~~~~

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