Цветовой баланс

// contest dp цветовой баланс http://contest.uni-smr.ac.ru/ru/problemset/6268/
# include <iostream>
# include <vector>

using namespace std;
struct dot
{
    int32_t previous = -1;
    int32_t count_0 = 0;
    int32_t count_1 = 0;
    int32_t res = 0;
};

int main() {
    int32_t n;
    cin >> n;
    vector<int32_t> a;
    vector<int32_t> b;
    vector<vector<dot>> dp(n);
    for (size_t i = 0; i < n; i++) {
        dp[i].resize(2);
    }
    for (size_t i = 0; i < n; i++) {
        int32_t cur;
        cin >> cur;
        a.push_back(cur);
    }
    for (size_t i = 0; i < n; i++) {
        int32_t cur;
        cin >> cur;
        b.push_back(cur);
    }
    dot x;
    x.count_0 = 1;
    dp[0][0] = x;
    x.count_0 = 0;
    x.count_1 = 1;
    dp[0][1] = x;
    for (size_t i = 1; i < n; i++) {
        x.res = 1000000000;
        if (dp[i - 1][0].count_0 - dp[i - 1][0].count_1 < 1) {
            x.res = max(dp[i - 1][0].res, abs(a[i] - a[i - 1]));
            x.previous = 0;
            x.count_0 = dp[i - 1][0].count_0 + 1;
            x.count_1 = dp[i - 1][0].count_1;
        }
        if (dp[i - 1][1].count_0 - dp[i - 1][1].count_1 < 1 && max(dp[i - 1][1].res, abs(a[i] - b[i - 1])) < x.res) {
            x.previous = 1;
            x.res = max(dp[i - 1][1].res, abs(a[i] - b[i - 1]));
            x.count_0 = dp[i - 1][1].count_0 + 1;
            x.count_1 = dp[i - 1][1].count_1;
        }
        dp[i][0] = x;
        x.res = 1000000000;
        if (dp[i - 1][0].count_1 - dp[i - 1][0].count_0 < 1) {
            x.res = max(dp[i - 1][0].res, abs(b[i] - a[i - 1]));
            x.previous = 0;
            x.count_0 = dp[i - 1][0].count_0;
            x.count_1 = dp[i - 1][0].count_1 + 1;
        }
        if (dp[i - 1][1].count_1 - dp[i - 1][1].count_0 < 1 && max(dp[i - 1][1].res, abs(b[i] - b[i - 1])) < x.res) {
            x.previous = 1;
            x.res = max(dp[i - 1][1].res, abs(b[i] - b[i - 1]));
            x.count_0 = dp[i - 1][1].count_0;
            x.count_1 = dp[i - 1][1].count_1 + 1;
        }
        dp[i][1] = x;
    }
    cout << min(dp[n - 1][0].res, dp[n - 1][1].res) << '\n';
    vector<int32_t> result;
    int32_t rs = 0;
    if (dp[n - 1][0].res > dp[n - 1][1].res) {
        rs = 1;
    }
    result.push_back(rs);
    for (int32_t i = n - 1; i > 0; i--) {
        rs = dp[i][rs].previous;
        result.push_back(rs);
    }
    for (int32_t i = n - 1; i >= 0; i--) {
        cout << result[i] + 1 << ' ';
    }
    return 0;
}