Submission #269540

#	Time	Username	Problem	Language	Result	Execution time	Memory
269540		hamerin	Wiring (IOI17_wiring)	C++17	100 / 100	136 ms	17764 KiB

wiring

#include "wiring.h"

#include <bits/stdc++.h>

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

using namespace std;

using i64 = long long;
using d64 = long double;
using pi = pair<int, int>;
using pli = pair<i64, i64>;
using ti = tuple<int, int, int>;
using tli = tuple<i64, i64, i64>;

#define iterall(cont) cont.begin(), cont.end()
#define prec(n) setprecision(n) << fixed

i64 inf = numeric_limits<i64>::max() / 3;

i64 min_total_length(vector<int> r, vector<int> b) {
    const int R = r.size();
    const int B = b.size();

    vector<i64> Rv, Bv;
    Rv.emplace_back(-inf);
    Bv.emplace_back(-inf);
    copy(iterall(r), back_inserter(Rv));
    copy(iterall(b), back_inserter(Bv));
    Rv.emplace_back(inf);
    Bv.emplace_back(inf);

    vector<pair<i64, bool>> seq;
    transform(iterall(r), back_inserter(seq),
              [](int x) -> decltype(seq)::value_type {
                  return {x, true};
              });
    transform(iterall(b), back_inserter(seq),
              [](int x) -> decltype(seq)::value_type {
                  return {x, false};
              });
    sort(iterall(seq),
         [](decltype(seq)::value_type l, decltype(seq)::value_type r) {
             return l.first < r.first;
         });

    int n = 1;
    vector<int> rhm(1, 0), bhm(1, 0);
    vector<i64> rs(1, 0), bs(1, 0);
    for (auto [el, clr] : seq) {
        if (clr)
            rhm.emplace_back(1);
        else
            rhm.emplace_back(0);

        if (!clr)
            bhm.emplace_back(1);
        else
            bhm.emplace_back(0);

        if (clr)
            rs.emplace_back(el);
        else
            rs.emplace_back(0);

        if (!clr)
            bs.emplace_back(el);
        else
            bs.emplace_back(0);

        rhm[n] += rhm[n - 1];
        bhm[n] += bhm[n - 1];
        rs[n] += rs[n - 1];
        bs[n] += bs[n - 1];
        ++n;
    }

    map<int, int> hmInterval;
    vector<i64> dp(R + B);

    hmInterval[0] = -1;
    for (int i = 0; i < R + B; i++) {
        auto [el, clr] = seq[i];

        i64 d;
        if (clr) {
            auto it = lower_bound(iterall(Bv), el);
            d = min((*it) - el, el - (*prev(it)));
        } else {
            auto it = lower_bound(iterall(Rv), el);
            d = min((*it) - el, el - (*prev(it)));
        }

        dp[i] = (i > 0 ? dp[i - 1] : 0) + d;

        auto it = hmInterval.find(rhm[i + 1] - bhm[i + 1]);
        if (it != hmInterval.end()) {
            auto j = it->second;
            dp[i] = min(dp[i],
                        (j >= 0 ? dp[j] : 0) +
                            abs(rs[i + 1] - rs[j + 1] - bs[i + 1] + bs[j + 1]));
        }
        hmInterval[rhm[i + 1] - bhm[i + 1]] = i;
    }

    return dp.back();
}

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