Submission #216848

#	Time	Username	Problem	Language	Result	Execution time	Memory
216848		emil_physmath	Wiring (IOI17_wiring)	C++17	13 / 100	36 ms	2688 KiB

wiring

#include "wiring.h"
#include <vector>
using namespace std;
using llong = long long;
const int maxN = 200000;

llong Solve1(vector<int> r, vector<int> b)
{
    if (r.back() > b[0]) return -1;
    llong ans = 0;
    for (int i: r)
        ans += b[0] - i;
    for (int i: b)
        ans += i - r.back();
    ans -= (llong)min(r.size(), b.size()) * llong(b[0] - r.back());
    return ans;
}

llong Solve2(vector<int> r, vector<int> b)
{
    int n = r.size() + b.size();
    vector<char> a(n);
    for (int i: r)
        if (1 <= i || i <= n) a[i - 1] = 'x';
        else return -1;
    for (int i: b)
        if (1 <= i || i <= n) a[i - 1] = 'o';
        else return -1;
    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 ? k - i + 1 : maxN, j + 1 < n ? j - k + 1 : maxN);
        i = j;
    }
    vector<int> mirror(n, -1);
    for (int i = 1; i < n; ++i)
        if (a[i] != a[i - 1])
        {
            int r = i, l = i - 1;
            while (true)
            {
                mirror[r] = l;
                if (!l || r + 1 == n || a[l - 1] != a[l] || a[r] != a[r + 1])
                    break;
                ++l; --r;
            }
        }
    vector<llong> dp(n);
    dp[0] = lone[0];
    for (int i = 1; i < n; ++i)
    {
        dp[i] = dp[i - 1] + lone[i];
        llong curdp = 0;
        if (mirror[i]) curdp += dp[mirror[i] - 1];
        int x = (i - mirror[i] + 1) / 2;
        curdp += (x * (x + 1LL)) / 2LL;
        curdp += (x * (x - 1LL)) / 2LL;
        dp[i] = min(dp[i], curdp);
    }
    return dp[n - 1];
}
llong min_total_length(vector<int> r, vector<int> b)
{
    llong res = Solve1(r, b);
    if (res != -1) return res;
    res = Solve2(r, b);
    if (res != -1) return res;
}

Compilation message (stderr)

wiring.cpp: In function 'llong min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:71:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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