Submission #1072611

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072611		ArthuroWich	Wiring (IOI17_wiring)	C++17	100 / 100	43 ms	13756 KiB

wiring

#include "wiring.h"
#include<bits/stdc++.h>
using namespace std;
#define int long long int
int pref[200005];
void init(int n, vector<pair<int, int>> &a) {
    for (int i = 1; i <= n; i++) {
        pref[i] = pref[i-1]+a[i-1].first;
    }
}
int query(int l, int r) {
    int x = min(l, r);
    r = max(l, r);
    l = x;
    l++;
    r++;
    return pref[r]-pref[l-1];
}
int calc(vector<int> &r, vector<int> &b) {
    int ans = 0, rbe, bbe;
    rbe = r.front();
    bbe = b.front();
    ans += query(b[0], b[min(r.size(), b.size())-1])-query(r[0], r[min(r.size(), b.size())-1]);
    if (r.size() < b.size()) {
        int x = b.size()-r.size();
        ans += query(b[r.size()], b[b.size()-1])-query(rbe, rbe)*x;
    } else if (r.size() > b.size()) {
        int x = (int)r.size()-b.size();
        ans += query(bbe, bbe)*x-query(r[b.size()], r[r.size()-1]);
    }
    return ans;
}
int min_total_length(vector<int32_t> R, vector<int32_t> B) {
    int n = R.size()+B.size();
    vector<pair<int, int>> a;
    for (int i = 0; i < R.size(); i++) {
        a.push_back({R[i], 0});
    }
    for (int i = 0; i < B.size(); i++) {
        a.push_back({B[i], 1});
    }
    vector<int> dp(n, INT64_MAX);
    sort(a.begin(), a.end());
    init(n, a);
    int l = -1, r = 0, l0;
    vector<int> lv, rv;
    bool f = 1;
    for (int i = 1; i < n; i++) {
        if (a[i].second != a[i-1].second) {
            lv.clear();
            rv.clear();
            l = i-1;
            l0 = i-1;
            r = i;
            if (dp[l0] == INT64_MAX) {
                for (int j = l0; j >= 0; j--) {
                    lv.push_back(j);
                }
            } else {
                int lm = l;
                for (int j = l; j >= 0; j--) {
                    if (a[l].second == a[j].second) {
                        lm = j;
                    } else {
                        break;
                    }
                }
                for (int j = lm; j <= l; j++) {
                    if (j == 0 || dp[j-1] == INT64_MAX) {
                        continue;
                    }
                    dp[j] = min(dp[j], dp[j-1]+a[i].first-a[j].first);
                }
                lv.push_back(l);
            }
            f = 0;
        } else {
            f = 1;
        }
        r = i;
        if (l == -1) {
            continue;
        }
        rv.push_back(i);
        if (dp[i-1] != INT64_MAX) {
            dp[i] = min(dp[i], dp[i-1]+abs(a[r].first-a[l0].first));
        }
        if (dp[l0] == INT64_MAX) {
            dp[i] = min(dp[i], calc(lv, rv));
        } else {
            if (f && l > 1 && dp[l-2] != INT64_MAX && a[l-1].second == a[l0].second) {
                lv.push_back(l-1);
                l--;
                dp[i] = min(dp[i], dp[l-1]+calc(lv, rv));
            } else if (dp[l-1] != INT64_MAX) {
                dp[i] = min(dp[i], dp[l-1]+calc(lv, rv));
            }
        }
        if ((i == n-1 || a[i].second != a[i+1].second) && dp[l0] != INT64_MAX) {
            if (dp[l-1] != INT64_MAX) {
                dp[i] = min(dp[i], dp[l-1]+calc(lv, rv));
            }
            while(l > 1 && dp[l-2] != INT64_MAX && a[l-1].second == a[l0].second) {
                lv.push_back(l-1);
                l--;
                dp[i] = min(dp[i], dp[l-1]+calc(lv, rv));
            }
            if (dp[l-1] != INT64_MAX) {
                dp[i] = min(dp[i], dp[l-1]+calc(lv, rv));
            }
        }
    }
    return dp[n-1];
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:36:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for (int i = 0; i < R.size(); i++) {
      |                     ~~^~~~~~~~~~
wiring.cpp:39:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for (int i = 0; i < B.size(); i++) {
      |                     ~~^~~~~~~~~~
wiring.cpp:86:59: warning: 'l0' may be used uninitialized in this function [-Wmaybe-uninitialized]
   86 |             dp[i] = min(dp[i], dp[i-1]+abs(a[r].first-a[l0].first));
      |                                                           ^

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