Submission #331703

#	Time	Username	Problem	Language	Result	Execution time	Memory
331703		ant101	Wiring (IOI17_wiring)	C++14	100 / 100	73 ms	15704 KiB

wiring

#include "wiring.h"
#include <iostream>
#include <algorithm>
#include <cstring>
#include <iomanip>
#include <fstream>
#include <cmath>
#include <vector>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <map>
#include <stack>
#include <queue>
#include <assert.h>
#include <limits>
#include <cstdio>
#include <complex>
using namespace std;

typedef long long ll;

vector<ll> seqinds;
vector<ll> prefl;
vector<ll> prefr;
vector<ll> dl;
vector<ll> dr;
vector<ll> len;

ll n;
ll ns;

ll INF = 1e18;

void processData(vector<int> &r, vector<int> &b){
    vector<pair<ll, bool>> seq;
    for (ll i : r) {
        seq.push_back({i, false});
    }
    for (ll i : b) {
        seq.push_back({i, true});
    }
    n = seq.size();
    sort(seq.begin(), seq.end());
    ll mx = seq.back().first;
    for (auto p : seq) {
        dl.push_back(p.first);
        dr.push_back(mx-p.first);
    }
    prefl.resize(n+1);
    prefr.resize(n+1);
    for (ll i = 0; i<n; i++){
        prefl[i+1] = prefl[i]+dl[i];
    }
    for (ll i = n-1; i>=0; i--){
        prefr[i] = prefr[i+1]+dr[i];
    }
    
    bool curval = seq[0].second;
    ll curind = 0;
    seqinds.push_back(curind);
    for (ll i = 0; i<n; i++) {
        if (seq[i].second != curval) {
            curind = i;
            seqinds.push_back(curind);
            curval = seq[i].second;
        }
    }
    ns = seqinds.size();
    seqinds.push_back(n);
    for (ll i = 0; i<seqinds.size()-1; i++) {
        len.push_back(seqinds[i+1]-seqinds[i]);
    }
}

//void processData2(vector<int> &r, vector<int> &b) {
//    vector<pair<ll, bool>> seq;
//    for (ll i : r) {
//        seq.push_back({i, false});
//    }
//    for (ll i : b) {
//        seq.push_back({i, true});
//    }
//    n = seq.size();
//    sort(seq.begin(), seq.end());
//    ll mx = seq.back().first;
//    for (auto p : seq) {
//        dl.push_back(p.first);
//        dr.push_back(mx-p.first);
//    }
//    prefl.resize(n+1);
//    prefr.resize(n+1);
//    for (ll i = 0; i<n; i++) {
//        prefl[i+1] = prefl[i]+dl[i];
//    }
//    for (ll i = n-1; )
//}

void display(string s, vector<ll> &v){
    cout << s << ": ";
    for (ll i : v) {
        cout << i << ' ';
    } cout << '\n';
}

ll lsum(ll i, ll l) {
    ll xi = seqinds[i];
    return prefl[xi+l]-prefl[xi]-l*dl[xi];
}

ll rsum(ll i, ll r) {
    ll xi1 = seqinds[i+1];
    return prefr[xi1-r]-prefr[xi1]-r*dr[xi1];
}

ll performDP() {
    ll mxlen = 0;
    for (ll i : len) {
        mxlen = max(mxlen, i);
    }
    vector<vector<ll>> dp(2, vector<ll>(mxlen+1, INF));
    vector<vector<ll>> dpgeq(2, vector<ll>(mxlen+1, INF));
    bool cur = false;
    dp[!cur][0] = 0;
    dpgeq[!cur][0] = 0;
    for (ll i = 0; i<ns; i++) {
        //cout<<"dp "<<i<<endl;
        ll xi1 = seqinds[i+1];
        ll ci = dr[xi1-1]-dr[xi1];
        ll minpref = INF;
        ll maxprev = max(len[i], ((i==0) ? 0 : len[i-1]));
        //ll maxprev = mxlen;
        for (ll r = 0; r<=maxprev; r++) {
            ll newl = len[i]-r;
            if (newl<0) {
                newl = 0;
            }
            ll newmin = dp[!cur][newl]+lsum(i, newl)+rsum(i, len[i]-newl)+ci*newl;
            //cout<<"at r = "<<r<<": new value is "<<newmin<<'\n';
            minpref = min(minpref,newmin);
            dp[cur][r] = minpref+ci*(r-len[i]);
        }
        if (i==ns-1) {
            break;
        }
        for (ll r = maxprev+1; r<=len[i+1]; r++) {
            dp[cur][r] = dp[cur][r-1]+ci;
        }
        /*for (ll x = 0; x<=max(maxprev,len[i+1]); x++){
         cout<<dp[cur][x]<<' ';
         }cout<<'\n';*/
        for (ll r = max(maxprev, len[i+1])-1; r>=0; r--) {
            dp[cur][r] = min(dp[cur][r], dp[cur][r+1]);
        }
        /*for (ll x = 0; x<=max(maxprev,len[i+1]); x++){
         cout<<dp[cur][x]<<' ';
         }cout<<'\n';*/
        cur=!cur;
    }
    /*for (int i = 0; i<ns; i++){
     for (int r = 0; r<mxlen; r++){
     //dp(i,r)
     for (int l = max(len[i]-r,0); l<=len[i]; l++){
     dp[cur][r]=min(dp[cur][r])
     }
     }
     }*/
    return dp[cur][0];
}

ll min_total_length(std::vector<int> r, std::vector<int> b) {
    processData(r,b);
    /*display("seqinds",seqinds);
     display("prefl",prefl);
     display("prefr",prefr);
     display("len",len);
     display("distance l",dl);
     display("distance r",dr);*/
    
    /*while (true){
     char c;
     ll a,b;
     cin>>c>>a>>b;
     if (c=='l'){
     cout<<lsum(a,b)<<endl;
     } else if (c=='r'){
     cout<<rsum(a,b)<<endl;
     } else {
     assert(1==0);
     }
     }*/
    return performDP();
}

Compilation message (stderr)

wiring.cpp: In function 'void processData(std::vector<int>&, std::vector<int>&)':
wiring.cpp:71:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for (ll i = 0; i<seqinds.size()-1; i++) {
      |                    ~^~~~~~~~~~~~~~~~~

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