Submission #540287

#	Time	Username	Problem	Language	Result	Execution time	Memory
540287		Deepesson	Wiring (IOI17_wiring)	C++17	0 / 100	1 ms	212 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:abreb)std::cout<<x<<" ";std::cout<<"\n";
        for(auto&x:fechar)somar+=x;
        for(auto&x:fechar)std::cout<<x<<" ";std::cout<<"\n";
        ll dif = myabs(abreb.size()-fechar.size());
        ans+=somar-somab;
        ///Proxima etapa: guloso retirando conexoes
        std::deque<ll> aa,ba;
        for(auto&x:abreb){
            aa.push_back(x+bestcusto(r,x));
        }
        for(auto&x:fechar){
            ba.push_back(bestcusto(b,x)-x);
        }
        std::sort(aa.begin(),aa.end());
        std::sort(ba.begin(),ba.end());
        for(int i=0;i!=aa.size();++i){
            if(aa[i]+ba[i]<0)ans+=aa[i]+ba[i];
        }
    }
    std::cout<<ans<<"!\n";
    ///Abre R com Fecha B
    {
        std::cout<<abrer.size()<<" "<<fechab.size()<<"\n";
        ll somab=0,somar=0;
        for(auto&x:abrer)somar+=x;
        for(auto&x:abrer)std::cout<<x<<" ";std::cout<<"\n";
        for(auto&x:fechab)somab+=x;
        for(auto&x:fechab)std::cout<<x<<" ";std::cout<<"\n";
        ll dif = myabs(abrer.size()-fechab.size());
        ans+=somab-somar;
        ///Proxima etapa: guloso retirando conexoes
        std::deque<ll> aa,ba;
        for(auto&x:abrer){
            aa.push_back(x+bestcusto(b,x));
        }
        for(auto&x:fechab){
            ba.push_back(bestcusto(r,x)-x);
        }
        std::sort(aa.begin(),aa.end());
        std::sort(ba.begin(),ba.end());
        for(int i=0;i!=aa.size();++i){
            if(aa[i]+ba[i]<0)ans+=aa[i]+ba[i];
        }
    }
    std::cout<<ans<<"!\n";
    return ans;
}

Compilation message (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:93:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   93 |         for(auto&x:abreb)std::cout<<x<<" ";std::cout<<"\n";
      |         ^~~
wiring.cpp:93:44: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   93 |         for(auto&x:abreb)std::cout<<x<<" ";std::cout<<"\n";
      |                                            ^~~
wiring.cpp:95:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   95 |         for(auto&x:fechar)std::cout<<x<<" ";std::cout<<"\n";
      |         ^~~
wiring.cpp:95:45: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   95 |         for(auto&x:fechar)std::cout<<x<<" ";std::cout<<"\n";
      |                                             ^~~
wiring.cpp:108:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |         for(int i=0;i!=aa.size();++i){
      |                     ~^~~~~~~~~~~
wiring.cpp:96:12: warning: unused variable 'dif' [-Wunused-variable]
   96 |         ll dif = myabs(abreb.size()-fechar.size());
      |            ^~~
wiring.cpp:118:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  118 |         for(auto&x:abrer)std::cout<<x<<" ";std::cout<<"\n";
      |         ^~~
wiring.cpp:118:44: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  118 |         for(auto&x:abrer)std::cout<<x<<" ";std::cout<<"\n";
      |                                            ^~~
wiring.cpp:120:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  120 |         for(auto&x:fechab)std::cout<<x<<" ";std::cout<<"\n";
      |         ^~~
wiring.cpp:120:45: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  120 |         for(auto&x:fechab)std::cout<<x<<" ";std::cout<<"\n";
      |                                             ^~~
wiring.cpp:133:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |         for(int i=0;i!=aa.size();++i){
      |                     ~^~~~~~~~~~~
wiring.cpp:121:12: warning: unused variable 'dif' [-Wunused-variable]
  121 |         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