Submission #216947

#	Time	Username	Problem	Language	Result	Execution time	Memory
216947		emil_physmath	Wiring (IOI17_wiring)	C++17	100 / 100	69 ms	11144 KiB

wiring

#include "wiring.h"
#include <algorithm>
#include <vector>
using namespace std;
using llong = long long;
const int inf = 1000'000'000;

llong min_total_length(vector<int> red, vector<int> blue)
{
    int n = red.size() + blue.size();
    vector<pair<int, char> > temp; temp.reserve(n);
    for (int i = 0; i < red.size(); ++i)
        temp.push_back({red[i], 'x'});
    for (int i = 0; i < blue.size(); ++i)
        temp.push_back({blue[i], 'o'});
    vector<char> a(n);
    vector<int> b(n);
    sort(temp.begin(), temp.end());
    for (int i = 0; i < n; ++i)
        b[i] = temp[i].first, a[i] = temp[i].second;
    vector<int> lone(n);
    for (int i = 0; i < n; ++i)
    {
        int j = i;
        while (j + 1 < n && a[j + 1] == a[i]) ++j;
        for (int k = i; k <= j; ++k)
            lone[k] = min(i ? b[k] - b[i - 1] : inf, j + 1 < n ? b[j + 1] - b[k] : inf);
        i = j;
    }
    vector<int> mirror(n, -1);
    vector<llong> mirrorval(n);
    for (int i = 1; i < n; ++i)
        if (a[i] != a[i - 1])
            for (int r = i, l = i - 1; 0 <= l && r < n && a[l] == a[i - 1] && a[r] == a[i]; --l, ++r)
            {
                mirror[r] = l;
                mirrorval[r] = b[r] - b[l];
                if (r > i)
                    mirrorval[r] += mirrorval[r - 1];
            }
    vector<llong> dp(n);
    dp[0] = lone[0];
    for (int i = 1; i < n; ++i)
    {
        dp[i] = dp[i - 1] + lone[i];
        if (mirror[i] == -1) continue;
        llong curdp = 0;
        curdp += (mirror[i] ? dp[mirror[i] - 1] : 0);
        curdp += mirrorval[i];
        dp[i] = min(dp[i], curdp);
    }
    return dp[n - 1];
}

Compilation message (stderr)

wiring.cpp: In function 'llong min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:12:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < red.size(); ++i)
                     ~~^~~~~~~~~~~~
wiring.cpp:14:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < blue.size(); ++i)
                     ~~^~~~~~~~~~~~~

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