Submission #624820

#	Time	Username	Problem	Language	Result	Execution time	Memory
624820		azberjibiou	Wiring (IOI17_wiring)	C++17	100 / 100	393 ms	54848 KiB

wiring

#include <bits/stdc++.h>
#include "wiring.h"
#define ll long long
#define pii pair<int, int>
#define fir first
#define sec second
using namespace std;
const int mxN=100010;
const ll INF=1e18;
int N, M;
vector <int> R, B;
vector <pii> RR, BB;
vector <ll> pR, pB;
map <pii, ll> dp;
ll myabs(ll a)  {return (a>0 ? a : -a);}
vector <pii> cr[2*mxN], cb[2*mxN];
ll sumR(int a, int b)
{
    if(a==0)    return pR[b];
    else    return pR[b]-pR[a-1];
}
ll sumB(int a, int b)
{
    if(a==0)    return pB[b];
    else    return pB[b]-pB[a-1];
}
ll f(int r, int b)
{
    pii now=pii(r, b);
    int nval=myabs(R[r]-B[b]);
    if(dp.find(now)!=dp.end())    return dp[now];
    if(r==N-1 && b==M-1)    return dp[now]=nval;
    ll ret=INF;
    if(R[r]>B[b])
    {
        if(b==M-1)  return dp[now]=f(r+1, b)+nval;
        if(r<N-1)
        {
            if(R[r+1]>B[b+1])
            {
                int cidx=r-b+mxN;
                int tmp=lower_bound(cr[cidx].begin(), cr[cidx].end(), now)-cr[cidx].begin();
                assert(cr[cidx][tmp]==now);
                tmp++;
                if(tmp!=cr[cidx].size())
                {
                    pii nxt=cr[cidx][tmp];
                    ret=min(ret, sumR(r, nxt.fir-1)-sumB(b, nxt.sec-1)+f(nxt.fir, nxt.sec));
                }
            }
            else    ret=min(ret, nval+f(r+1, b+1)), ret=min(ret, nval+f(r+1, b));
        }
        ret=min(ret, nval+f(r, b+1));
        //printf("dp[%d, %d]=%lld\n", r, b, ret);
        return dp[now]=ret;
    }
    else
    {
        if(r==N-1)  return dp[now]=f(r, b+1)+nval;
        if(b<M-1)
        {
            if(R[r+1]<B[b+1])
            {
                int cidx=r-b+mxN;
                int tmp=lower_bound(cb[cidx].begin(), cb[cidx].end(), now)-cb[cidx].begin();
                assert(cb[cidx][tmp]==now);
                tmp++;
                if(tmp!=cb[cidx].size())
                {
                    pii nxt=cb[cidx][tmp];
                    ret=min(ret, sumB(b, nxt.sec-1)-sumR(r, nxt.fir-1)+f(nxt.fir, nxt.sec));
                }
            }
            else    ret=min(ret, nval+f(r+1, b+1)), ret=min(ret, nval+f(r, b+1));
        }
        ret=min(ret, nval+f(r+1, b));
        //printf("dp[%d, %d]=%lld\n", r, b, ret);
        return dp[now]=ret;
    }
}
ll min_total_length(vector<int> r, vector<int> b) {
    N=r.size(), M=b.size();
    R=r;    B=b;
    pR.resize(N);
    pB.resize(M);
    pR[0]=R[0];
    for(int i=1;i<N;i++)    pR[i]=pR[i-1]+R[i];
    pB[0]=B[0];
    for(int i=1;i<M;i++)    pB[i]=pB[i-1]+B[i];
    for(int i=0;i<N;i++)
    {
        int pos=lower_bound(B.begin(), B.end(), R[i])-B.begin();
        if(pos!=M)  BB.emplace_back(i, pos);
        if(pos!=0)  RR.emplace_back(i, pos-1);
    }
    for(int i=0;i<M;i++)
    {
        int pos=lower_bound(R.begin(), R.end(), B[i])-R.begin();
        if(pos!=N)  RR.emplace_back(pos, i);
        if(pos!=0)  BB.emplace_back(pos-1, i);
    }
    sort(RR.begin(), RR.end());
    sort(BB.begin(), BB.end());
    RR.erase(unique(RR.begin(), RR.end()), RR.end());
    BB.erase(unique(BB.begin(), BB.end()), BB.end());
    /*printf("RR");
    for(pii ele : RR)   printf("(%d, %d) ", ele.fir, ele.sec);
    printf("\nBB");
    for(pii ele : BB)   printf("(%d, %d) ", ele.fir, ele.sec);
    printf("\n");*/
    for(pii ele : RR)   cr[mxN+ele.fir-ele.sec].push_back(ele);
    for(pii ele : BB)   cb[mxN+ele.fir-ele.sec].push_back(ele);
    return f(0, 0);
}
/*
4 5
1 2 3 7
0 4 5 9 10
*/

Compilation message (stderr)

wiring.cpp: In function 'long long int f(int, int)':
wiring.cpp:45:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |                 if(tmp!=cr[cidx].size())
      |                    ~~~^~~~~~~~~~~~~~~~~
wiring.cpp:68:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |                 if(tmp!=cb[cidx].size())
      |                    ~~~^~~~~~~~~~~~~~~~~

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