Submission #129642

#	Time	Username	Problem	Language	Result	Execution time	Memory
129642		tri	Wiring (IOI17_wiring)	C++14	100 / 100	74 ms	11500 KiB

wiring

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;

#define pb push_back
#define f first
#define s second

namespace debug {
    const int DEBUG = true;

    template<class T1, class T2>
    void pr(const pair<T1, T2> &x);

    template<class T, size_t SZ>
    void pr(const array<T, SZ> &x);

    template<class T>
    void pr(const vector<T> &x);

    template<class T>
    void pr(const set<T> &x);

    template<class T1, class T2>
    void pr(const map<T1, T2> &x);

    template<class T>
    void pr(const T &x) { if (DEBUG) cout << x; }

    template<class T, class... Ts>
    void pr(const T &first, const Ts &... rest) { pr(first), pr(rest...); }

    template<class T1, class T2>
    void pr(const pair<T1, T2> &x) { pr("{", x.f, ", ", x.s, "}"); }

    template<class T>
    void prIn(const T &x) {
        pr("{");
        bool fst = 1;
        for (auto &a : x) {
            pr(fst ? "" : ", ", a), fst = 0;
        }
        pr("}");
    }

    template<class T, size_t SZ>
    void pr(const array<T, SZ> &x) { prIn(x); }

    template<class T>
    void pr(const vector<T> &x) { prIn(x); }

    template<class T>
    void pr(const set<T> &x) { prIn(x); }

    template<class T1, class T2>
    void pr(const map<T1, T2> &x) { prIn(x); }

    void ps() { pr("\n"); }

    template<class Arg, class... Args>
    void ps(const Arg &first, const Args &... rest) {
        pr(first, " ");
        ps(rest...);
    }
}
using namespace debug;

const ll INF = 1e17;

void mineq(ll &a, ll b) {
    if (b < a) a = b;
}

vl pSum;

ll fSum(int l, int r) {
    return l == 0 ? pSum[r] : pSum[r] - pSum[l - 1];
}


ll min_total_length(vi r, vi b) {
    vector<pi> pts;
    for (int i : r) {
        pts.pb({i, 0});
    }
    for (int i : b) {
        pts.pb({i, 1});
    }
    sort(pts.begin(), pts.end());

    vi gSz;
    vi gSt;

    for (int i = 0; i < pts.size(); i++) {
        if (i == 0 || pts[i].s != pts[i - 1].s) {
            gSz.pb(1);
            gSt.pb(i);
        } else {
            gSz[gSz.size() - 1]++;
        }
    }

    int nG = gSz.size();

    pSum.resize(pts.size());
    pSum[0] = pts[0].f;
    for (int i = 1; i < pts.size(); i++) {
        pSum[i] = pSum[i - 1] + pts[i].f;
    }

    vector<vl> dp(nG);
    for (int i = 0; i < nG; i++) {
        dp[i].resize(gSz[i] + 1, INF);
    }

    dp[0][0] = 0;

    for (int cG = 0; cG < nG - 1; cG++) {

        // match current unmatched with first index of next group
        for (int m = 0; m < gSz[cG]; m++) {
            mineq(dp[cG][m + 1], dp[cG][m] + (pts[gSt[cG + 1]].f - pts[gSt[cG] + m].f));
        }

        // match remaining unmatched with next group
        for (int m = max(0, gSz[cG] - gSz[cG + 1]); m <= gSz[cG]; m++) {
            int nM = gSz[cG] - m;
            mineq(dp[cG + 1][nM],
                  dp[cG][m] + (fSum(gSt[cG + 1], gSt[cG + 1] + nM - 1) - fSum(gSt[cG] + m, gSt[cG + 1] - 1)));
        }

        // match next unmatched with last index of current group
        for (int m = 0; m < gSz[cG + 1]; m++) {
            mineq(dp[cG + 1][m + 1], dp[cG + 1][m] + (pts[gSt[cG + 1] + m].f - pts[gSt[cG + 1] - 1].f));
        }
    }

    return dp[nG - 1][gSz[nG - 1]];
}

Compilation message (stderr)

wiring.cpp: In function 'll min_total_length(vi, vi)':
wiring.cpp:103:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < pts.size(); i++) {
                     ~~^~~~~~~~~~~~
wiring.cpp:116:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i < pts.size(); i++) {
                     ~~^~~~~~~~~~~~

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