Submission #879078

#	Time	Username	Problem	Language	Result	Execution time	Memory
879078		snpmrnhlol	Wiring (IOI17_wiring)	C++17	100 / 100	40 ms	10180 KiB

wiring

#include "wiring.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1e5;
const ll inf = 1e18;
vector <ll> a;
vector <ll> c;
struct p{
    ll nr,tip;
}v[2*N];
ll dp[2*N];
ll ps[2*N + 1];
ll sum(ll l,ll r){
    return ps[r + 1] - ps[l];
}
ll min_total_length(vector <int> r,vector <int> b){
    ll n = 0;
    for(ll i = 0;i < r.size();i++){
        v[n++] = {r[i],0};
    }
    for(ll i = 0;i < b.size();i++){
        v[n++] = {b[i],1};
    }
    sort(v,v + n,[&](p a,p b){
         return a.nr < b.nr;
    });
    for(ll i = 0;i < n;i++){
        ps[i + 1] = ps[i] + v[i].nr;
        dp[i] = inf;
    }
    ll i = 0,p = -1;
    while(i < n){
        ll nxt = i;
        while(nxt < n - 1 && v[i].tip == v[nxt + 1].tip)nxt++;
        if(p != -1){
            ///p index of first red
            ///i index of first blue
            ///nxt index of last blue
            ///case 1: right side bigger
            ll l = i - 1;
            ll r = i;
            ll cross = (v[i].nr - v[i - 1].nr);
            ll minn = inf;
            while(l >= p && r <= nxt){
                minn = min(minn,(l == 0?0:dp[l - 1]) + ((i - l)*v[i - 1].nr - sum(l,i - 1)));
                //cout<<minn<<' '<<(r - i + 1)*cross<<' '<<sum(i,r)<<' '<<'\n';
                dp[r] = min(dp[r],(r - i + 1)*cross + (sum(i,r) - v[i].nr*(r - i + 1)) + minn);
                l--;r++;
            }
            while(r <= nxt){
                //cout<<minn<<' '<<(r - i + 1)*cross<<' '<<sum(i,r)<<' '<<'\n';
                dp[r] = min(dp[r],(r - i + 1)*cross + (sum(i,r) - v[i].nr*(r - i + 1)) + minn);
                r++;
            }

            ///case 2:left side bigger
            l = p;
            r = nxt;
            minn = inf;
            while(i - 1 - l > r - i){
                minn = min(minn,(l == 0?0:dp[l - 1]) + (i - l)*cross + v[i - 1].nr*(i - l) - sum(l,i - 1));
                l++;
            }
            while(i - 1 - l < r - i){
                r--;
            }
            while(l < i && r > i - 1){
                minn = min(minn,(l == 0?0:dp[l - 1]) + (i - l)*cross + v[i - 1].nr*(i - l) - sum(l,i - 1));
                //cout<<r<<' '<<minn<<' '<<sum(i,r)<<' '<<v[i].nr*(r - i + 1)<<'\n';
                dp[r] = min(dp[r],sum(i,r) - v[i].nr*(r - i + 1) + minn);
                l++;
                r--;
            }
            //cout<<nxt<<' '<<p<<'\n';
            for(ll j = nxt - 1;j >= p;j--)dp[j] = min(dp[j],dp[j + 1]);
            /*for(ll j = 0;j < n;j++){
                cout<<dp[j]<<' ';
            }
            cout<<'\n';*/
        }
        p = i;
        i = nxt;
        i++;
    }
    return dp[n - 1];
}
/**
int main(){
    ll n,m;
    cin>>n>>m;
    a.resize(n);
    c.resize(m);
    for(ll i = 0;i < n;i++){
        cin>>a[i];
    }
    for(ll i = 0;i < m;i++){
        cin>>c[i];
    }
    min_total_length(a,c);
    return 0;
}
**/
/**
10 11
1 2 3 4 7 8 9 10 11 15
5 6 12 13 14 16 17 18 19 20 21
**/

Compilation message (stderr)

wiring.cpp: In function 'll min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:19:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     for(ll i = 0;i < r.size();i++){
      |                  ~~^~~~~~~~~~
wiring.cpp:22:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for(ll i = 0;i < b.size();i++){
      |                  ~~^~~~~~~~~~

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