Submission #159608

#	Time	Username	Problem	Language	Result	Execution time	Memory
159608		rama_pang	Wiring (IOI17_wiring)	C++14	100 / 100	124 ms	42744 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
const lint INF = 1e18;

vector<vector<lint>> memo;
vector<vector<lint>> cluster;
vector<lint> G(1), D(1);

inline lint connect(int le, int ri) { // connect two points: le and ri
    return (le <= 0)? INF : (D[ri] - D[ri - 1] - D[le] + D[le - 1]);
}

inline lint connect_all(int le, int mid, int ri) { // connect all points between le and ri, with mid as pivot (the last element of previous group)
    return (le <= 0)? INF : (D[ri] - D[mid] - D[mid] + D[le - 1]);
}

inline int get_index(int group, lint plus_minus) {
    return G[group] + plus_minus;
}

lint dp(int group, int previous_left) {
    if (previous_left < 0) return INF;
    if (memo[group][previous_left] != -1) return memo[group][previous_left];

    lint &res = memo[group][previous_left];
    res = INF;

    /* connect leftmost unpaired point of previous group with leftmost popint of current group */
    if (group < cluster.size() && previous_left > 0) 
        res = min(res, dp(group, previous_left - 1) + connect(get_index(group - 1, 1 - previous_left), get_index(group - 1, 1)));

    /* connect leftmost unpaired point of previous group with rightmost point of the group before it */
    if (group > 2 && previous_left > 0) 
        res = min(res, dp(group, previous_left - 1) + connect(get_index(group - 2, 0), get_index(group - 1, 1 - previous_left)));

    /* connect all unpaired points in the previous group with the prefix of points in the current group */
    if (group < cluster.size()) 
        res = min(res, dp(group + 1, cluster[group].size() - previous_left) + 
        connect_all(get_index(group - 1, 1 - previous_left), get_index(group - 1, 0), get_index(group - 1, previous_left)));

    /* base case: all pairs of wires are already connected */
    if (group == cluster.size() && previous_left == 0) 
        res = 0;

    return res;
}

lint min_total_length(vector<int> r, vector<int> b) {
    int N = r.size() + b.size();

    vector<pair<lint, char>> all_wires(N), red, blue;
    for (auto i : r) red.push_back({i + 1, 'r'});
    for (auto i : b) blue.push_back({i + 1, 'b'});
    merge(red.begin(), red.end(), blue.begin(), blue.end(), all_wires.begin());

    cluster.emplace_back(); 
    cluster[0].emplace_back(0);
    for (int i = 0; i < N; i++) {
        int le = i;
        while (i + 1 < N && all_wires[i + 1].second == all_wires[le].second) i++;
        int ri = i;
        cluster.emplace_back();
        for (int j = le; j <= ri; j++) {
            cluster.back().emplace_back(all_wires[j].first);
        }
    }

    /* make DP table */
    memo.resize(cluster.size() + 1);
    for (int i = 1; i <= cluster.size(); i++) memo[i].assign(cluster[i - 1].size() + 1, -1);
    
    /* G = prefix sum of group size, D = prefix sum of x-coordinates */
    G[0] = D[0] = 0;
    for (int i = 1; i < cluster.size(); i++) G.push_back(G.back() + cluster[i].size());
    G.push_back(G.back());
    for (int i = 1; i < cluster.size(); i++) for (auto j : cluster[i]) D.push_back(D.back() + j);

    return dp(1, 0);
}

Compilation message (stderr)

wiring.cpp: In function 'lint dp(int, int)':
wiring.cpp:31:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (group < cluster.size() && previous_left > 0) 
         ~~~~~~^~~~~~~~~~~~~~~~
wiring.cpp:39:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (group < cluster.size()) 
         ~~~~~~^~~~~~~~~~~~~~~~
wiring.cpp:44:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (group == cluster.size() && previous_left == 0) 
         ~~~~~~^~~~~~~~~~~~~~~~~
wiring.cpp: In function 'lint min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:72:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i <= cluster.size(); i++) memo[i].assign(cluster[i - 1].size() + 1, -1);
                     ~~^~~~~~~~~~~~~~~~~
wiring.cpp:76:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i < cluster.size(); i++) G.push_back(G.back() + cluster[i].size());
                     ~~^~~~~~~~~~~~~~~~
wiring.cpp:78:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i < cluster.size(); i++) for (auto j : cluster[i]) D.push_back(D.back() + j);
                     ~~^~~~~~~~~~~~~~~~

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