Submission #431943

#	Time	Username	Problem	Language	Result	Execution time	Memory
431943		plekkpea	Wiring (IOI17_wiring)	C++14	100 / 100	63 ms	8716 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<pair<ll,ll> > p;
ll x,vah[200005],l,y,v1,v2,k,z;
bool bb;

ll min_total_length(vector<int> r, vector<int> b) {
    for(int i=0; i<r.size(); i++) p.push_back({r[i],0});
    for(int i=0; i<b.size(); i++) p.push_back({b[i],1});
    sort(p.begin(),p.end());
    x=0;
    for(int i=0; i<p.size(); i++) if(p[0].second==p[i].second){
        vah[i+1]=1e17;
        l=i;
    }
    else break;
    vah[0]=0;
    l++;
    for(int i=l; i<p.size(); i++){
        bb=0;
        if(i==l || p[x].second==p[i].second) bb=1;
        while(p[x].second==p[i].second) x++;
        if(bb){
            ll su=0;
            v2=1e17;
            z=i-1;
            if(x!=z){
                for(int j=z; j>=x; j--){
                    su+=p[i].first-p[j].first;
                    if(su+vah[j]<=v2) v2=su+vah[j],k=j;
                }
                y=k;
                vah[i+1]=v2;
            }
            else{
                vah[i+1]=min(vah[i],vah[i-1])+p[i].first-p[z].first;
            }
        }
        else if(x!=z){
            if((z-y+1)>=(i-z)) v1=vah[i]+p[i].first-p[z+1].first;
            else v1=vah[i]+p[i].first-p[z].first;
            if(y>x) v2=vah[i]+p[i].first-p[y-1].first+vah[y-1]-vah[y];
            else v2=1e17;
            if(v2<v1) y--,vah[i+1]=v2;
            else vah[i+1]=v1;
        }
        else{
            vah[i+1]=vah[i]+p[i].first-p[z].first;
        }
        //cout<<p[i].first<<" "<<x<<" "<<y<<" "<<z<<"\n";
    }
    /*for(int i=0; i<=r.size()+b.size(); i++) cout<<vah[i]<<" ";
    cout<<"\n";*/
	return vah[r.size()+b.size()];
}

Compilation message (stderr)

wiring.cpp: In function 'll min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:10:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |     for(int i=0; i<r.size(); i++) p.push_back({r[i],0});
      |                  ~^~~~~~~~~
wiring.cpp:11:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |     for(int i=0; i<b.size(); i++) p.push_back({b[i],1});
      |                  ~^~~~~~~~~
wiring.cpp:14:19: 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]
   14 |     for(int i=0; i<p.size(); i++) if(p[0].second==p[i].second){
      |                  ~^~~~~~~~~
wiring.cpp:21:19: 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]
   21 |     for(int i=l; i<p.size(); i++){
      |                  ~^~~~~~~~~

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