Submission #1196405

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196405		Aviansh	Wiring (IOI17_wiring)	C++20	100 / 100	27 ms	5416 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>

using namespace std;

long long min_total_length(vector<int> r, vector<int> b) {
    int n = r.size();
    int m = b.size();
    vector<pair<int,bool>>both(n+m);// red is true
    int i = 0;
    int j = 0;
    int prevr = -1e9;
    int prevb = -1e9;
    int closest[n+m];
    while(i<n||j<m){
        if(i<n&&j<m){
            if(r[i]<b[j]){
                both[i+j].first=r[i];
                both[i+j].second=true;
                prevr = r[i];
                closest[i+j]=r[i]-prevb;
                i++;
            }
            else{
                both[i+j].first=b[j];
                prevb=b[j];
                closest[i+j]=b[j]-prevr;
                both[i+j].second=false;
                j++;
            }
        }
        else if(i<n){
            both[i+j].first=r[i];
            both[i+j].second=true;
            prevr = r[i];
            closest[i+j]=r[i]-prevb;
            i++;
        }
        else{
            both[i+j].first=b[j];
            prevb=b[j];
            closest[i+j]=b[j]-prevr;
            both[i+j].second=false;
            j++;
        }
    }
    prevr = 2e9;
    prevb = 2e9;
    for(int i = n+m-1;i>=0;i--){
        if(both[i].second){
            //is red
            closest[i]=min(closest[i],prevb-both[i].first);
            prevr = both[i].first;
        }
        else {
            //is blue
            closest[i]=min(closest[i],prevr-both[i].first);
            prevb = both[i].first;
        }
    }
    //closest done
    long long ans = 0;
    priority_queue<int,vector<int>,greater<int>>pqr,pqb;
    for(int i = 0;i<n+m;i++){
        if(both[i].second){
            //red
            if(pqb.size()==0||closest[i]<both[i].first+pqb.top()){
                ans+=closest[i];
                pqr.push(-closest[i]-both[i].first);
            }
            else{
                int a = pqb.top();
                pqb.pop();
                ans+=both[i].first+a;
                pqr.push({-both[i].first-a-both[i].first});
            }
        }
        else{
            //blue
            if(pqr.size()==0||closest[i]<both[i].first+pqr.top()){
                ans+=closest[i];
                pqb.push(-closest[i]-both[i].first);
            }
            else{
                int a = pqr.top();
                pqr.pop();
                ans+=both[i].first+a;
                pqb.push({-both[i].first-a-both[i].first});
            }
        }
    }
    return ans;
}

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