Submission #47222

#	Time	Username	Problem	Language	Result	Execution time	Memory
47222		dqhungdl	Wiring (IOI17_wiring)	C++17	0 / 100	45 ms	5892 KiB

wiring

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

int64_t m=0,n=0,a[100005],b[100005],Pre[100005],Edge[100005];

int64_t Binary1(int64_t x)
{
    int64_t rs=-1,l=1,r=m;
    while(l<=r)
    {
        int64_t mid=(l+r)/2;
        if(a[mid]<x)
        {
            rs=mid;
            l=mid+1;
        }
        else
            r=mid-1;
    }
    return rs;
}

int64_t Binary2(int64_t x)
{
    int64_t rs=-1,l=1,r=m;
    while(l<=r)
    {
        int64_t mid=(l+r)/2;
        if(a[mid]>x)
        {
            rs=mid;
            r=mid-1;
        }
        else
            l=mid+1;
    }
    return rs;
}

int64_t Binary3(int64_t x)
{
    int64_t rs=-1,l=1,r=n;
    while(l<=r)
    {
        int64_t mid=(l+r)/2;
        if(b[mid]<x)
        {
            rs=mid;
            l=mid+1;
        }
        else
            r=mid-1;
    }
    return rs;
}

int64_t Binary4(int64_t x)
{
    int64_t rs=-1,l=1,r=n;
    while(l<=r)
    {
        int64_t mid=(l+r)/2;
        if(b[mid]>x)
        {
            rs=mid;
            r=mid-1;
        }
        else
            l=mid+1;
    }
    return rs;
}

long long min_total_length(vector<int> A,vector<int> B)
{
    for(int64_t i=0;i<A.size();i++)
        a[++m]=A[i];
    for(int64_t i=0;i<B.size();i++)
        b[++n]=B[i];
    int64_t res=0;
    for(int64_t i=1;i<=n;i++)
    {
        int64_t t1=Binary1(b[i]);
        int64_t t2=Binary2(b[i]);
        if(t2==-1)
        {
            res+=b[i]-a[t1];
            Pre[i]=t1;
            Edge[t1]++;
        }
        else
        if(t1==-1)
        {
            res+=a[t2]-b[i];
            Pre[i]=t2;
            Edge[t2]++;
        }
        else
        if(b[i]-a[t1]<a[t2]-b[i])
        {
            res+=b[i]-a[t1];
            Pre[i]=t1;
            Edge[t1]++;
        }
        else
        {
            res+=a[t2]-b[i];
            Pre[i]=t2;
            Edge[t2]++;
        }
    }
    for(int64_t i=1;i<=m;i++)
        if(Edge[i]==0)
        {
            int64_t t1=Binary3(a[i]);
            int64_t t2=Binary4(a[i]);
            int64_t c1=1e10,c2=1e10;
            if(t1!=-1)
            {
                c1=a[i]-b[t1];
                if(Pre[t1]!=0&&Edge[Pre[t1]]>1)
                    c1-=abs(b[t1]-a[Pre[t1]]);
            }
            if(t2!=-1)
            {
                c2=b[t2]-a[i];
                if(Pre[t2]!=0&&Edge[Pre[t2]]>1)
                    c2-=abs(a[Pre[t2]]-b[t2]);
            }
            res+=min(c1,c2);
            if(c1<c2)
                Pre[t1]=0;
            else
                Pre[t2]=0;
        }
    return res;
}

/*int main()
{
    ios_base::sync_with_stdio(false);
    freopen("TEST.INP","r",stdin);
    int64_t mm,nn,x;
    vector<int64_t> A,B;
    cin>>mm>>nn;
    while(mm--)
    {
        cin>>x;
        A.push_back(x);
    }
    while(nn--)
    {
        cin>>x;
        B.push_back(x);
    }
    cout<<min_total_length(A,B);
}*/

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:77:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int64_t i=0;i<A.size();i++)
                     ~^~~~~~~~~
wiring.cpp:79:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int64_t i=0;i<B.size();i++)
                     ~^~~~~~~~~

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