Submission #660588

#	Time	Username	Problem	Language	Result	Execution time	Memory
660588		Banan	Wiring (IOI17_wiring)	C++17	13 / 100	138 ms	17736 KiB

wiring

#include "wiring.h"

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
#define double long double
#define endl '\n'
#define sz(a) (int)a.size()
#define pb push_back
#define fs first
#define sc second
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
ll const INF = LONG_LONG_MAX;



long long min_total_length(std::vector<int> r, std::vector<int> b) {

    ll n=sz(r), m=sz(b);
    if(n>m){swap(n, m);swap(r, b);}

    set<ll> incr;
    set<ll, greater<>> decr;
    for(int i=0;i<m;i++)
    {
        incr.insert(b[i]);
        decr.insert(b[i]);
    }
    map<ll, bool> mark;
    ll ans=0;
    set<ll> s;
    for(int i=0;i<n;i++)
    {
        auto it1=incr.lower_bound(r[i]), it2=decr.lower_bound(r[i]);
        ll v1=(*it1), v2=(*it2);
        if(it1==incr.end()){v1=INF;}
        if(it2==decr.end()){v2=INF;}
        if(abs(v1-r[i])==abs(v2-r[i]))
        {
            s.insert(v2);
            incr.erase(v2);
            decr.erase(v2);
            mark[v2]=1;
        }
        else if(abs(v1-r[i])<abs(v2-r[i]))
        {
            s.insert(v1);
            incr.erase(v1);
            decr.erase(v1);
            mark[v1]=1;
        }
        else if(abs(v1-r[i])>abs(v2-r[i]))
        {
            s.insert(v2);
            incr.erase(v2);
            decr.erase(v2);
            mark[v2]=1;
        }
    }
    auto it=s.begin();
    for(int i=0;i<n;i++)
    {
        ll val=(*it);
        ans+=abs(r[i]-val);
        it++;
    }

    for(int i=0;i<m;i++)
    {
        if(!mark[b[i]])
        {
            ll lo=0, hi=n-1, mid=(lo+hi)/2, ind1=-1;
            while(lo<=hi)
            {
                if(r[mid]<b[i]){ind1=mid;lo=mid+1;mid=(lo+hi)/2;}
                else{hi=mid-1;mid=(lo+hi)/2;}
            }
            lo=0, hi=n-1, mid=(lo+hi)/2;
            ll ind2=-1;
            while(lo<=hi)
            {
                if(r[mid]>b[i]){ind2=mid;hi=mid-1;mid=(lo+hi)/2;}
                else{lo=mid+1;mid=(lo+hi)/2;}
            }
            if(ind1==-1){ans+=abs(r[ind2]-b[i]);}
            else if(ind2==-1){ans+=abs(r[ind1]-b[i]);}
            else{ans+=min(abs(r[ind2]-b[i]), abs(r[ind1]-b[i]));}
        }
    }

	return ans;
}

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