제출 #159594

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
159594		rama_pang	전선 연결 (IOI17_wiring)	C++14	100 / 100	101 ms	42600 KiB

wiring

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

struct wire {
    lint x;
    int id;
    char color;
    bool operator < (const wire &o) const {
        return x < o.x;
    }

};

vector<vector<lint>> memo;
vector<vector<lint>> cluster;
vector<lint> group_size_prefix(1), dist_prefix(1);

inline void precompute() {
    group_size_prefix[0] = 0;
    for (int i = 1; i < cluster.size(); i++) {
        group_size_prefix.push_back(group_size_prefix.back() + cluster[i].size());
    }
    group_size_prefix.push_back(group_size_prefix.back());

    dist_prefix[0] = 0;
    for (int i = 1; i < cluster.size(); i++) {
        for (auto j : cluster[i]) {
            dist_prefix.push_back(dist_prefix.back() + j);
        }
    }
}

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

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)
    if (le <= 0) return INF;
    lint res = 0;
    res += dist_prefix[ri] - dist_prefix[mid];
    res -= dist_prefix[mid] - dist_prefix[le - 1];
    return res;
}

inline int get_index(int group, lint prev) {
    return group_size_prefix[group] - prev;
}

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

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

    if (group >= cluster.size()) {
        if (group > 2 && previous_left > 0) res = dp(group, previous_left - 1) + connect(get_index(group - 2, 0), get_index(group - 1, previous_left - 1));
        else res = 0;
        return res;
    }

    res = INF;
    
    /* connect leftmost unpaired point of previous group with leftmost popint of current group */
    res = min(res, dp(group, previous_left - 1) + connect(get_index(group - 1, previous_left - 1), get_index(group - 1, -1)));

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

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

    
    return res;
}

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

    vector<wire> all_wires(N), red, blue;
    for (auto i : r) red.push_back({i + 1, -1, 'r'});
    for (auto i : b) blue.push_back({i + 1, -1, 'b'});
    merge(red.begin(), red.end(), blue.begin(), blue.end(), all_wires.begin());
    for (int i = 0; i < N; i++) all_wires[i].id = i;

    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].color == all_wires[le].color) i++;
        int ri = i;
        cluster.emplace_back();
        for (int j = le; j <= ri; j++) {
            cluster.back().emplace_back(all_wires[j].x);
        }
    }

    memo.resize(cluster.size() + 1);
    for (int i = 1; i <= cluster.size(); i++) {
        memo[i].assign(cluster[i - 1].size() + 1, -1);
    }

    precompute();

    return dp(1, 0);
}

컴파일 시 표준 에러 (stderr) 메시지

wiring.cpp: In function 'void precompute()':
wiring.cpp:23:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i < cluster.size(); i++) {
                     ~~^~~~~~~~~~~~~~~~
wiring.cpp:29:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i < cluster.size(); i++) {
                     ~~^~~~~~~~~~~~~~~~
wiring.cpp: In function 'lint dp(int, int)':
wiring.cpp:63:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (group >= cluster.size()) {
         ~~~~~~^~~~~~~~~~~~~~~~~
wiring.cpp: In function 'lint min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:107:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i <= cluster.size(); i++) {
                     ~~^~~~~~~~~~~~~~~~~

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