Submission #639345

#	Time	Username	Problem	Language	Result	Execution time	Memory
639345		piOOE	Paint By Numbers (IOI16_paint)	C++17	100 / 100	726 ms	91080 KiB

paint

#include <bits/stdc++.h>
#include "paint.h"

using namespace std;

string solve_puzzle(string s, vector<int> c) {
    s = "__" + s + "__";
    int n = s.size(), k = c.size();

    vector<int> nxtWhite(n + 1, n), nxtBlack(n + 1, n), prvBlack(n + 1, -1);
    auto canWhite = [&](int l, int r) { //[l, r)
        assert(l < r);
        return nxtBlack[l] >= r;
    };
    auto canBlack = [&](int l, int r) { //[l, r)
        assert(l < r);
        return nxtWhite[l] >= r;
    };
    for (int i = n - 1; i > -1; --i) {
        nxtBlack[i] = nxtBlack[i + 1];
        nxtWhite[i] = nxtWhite[i + 1];
        if (s[i] == '_') {
            nxtWhite[i] = i;
        } else if (s[i] == 'X') {
            nxtBlack[i] = i;
        }
    }
    for (int i = 0; i < n; ++i) {
        if (i > 0) {
            prvBlack[i] = prvBlack[i - 1];
        }
        if (s[i] == 'X') {
            prvBlack[i] = i;
        }
    }

    vector pref(k + 1, vector<bool>(n + 1)), suf(k + 1, vector<bool>(n + 1));
    fill(pref[0].begin(), pref[0].begin() + nxtBlack[0], true), fill(suf[k].begin() + prvBlack[n - 1] + 1, suf[k].end(),
                                                                     true);
    vector<int> prefSum(k + 1), sufSum(k + 1);
    for (int i = 0; i < k; ++i) {
        prefSum[i + 1] = prefSum[i] + c[i];
    }
    for (int i = k - 1; i > -1; --i) {
        sufSum[i] = sufSum[i + 1] + c[i];
    }

    vector<int> lazyWhite(n + 1), lazyBlack(n + 1);
    auto setBlack = [&](int l, int r) { //[l, r)
        lazyBlack[l] += 1;
        lazyBlack[r] -= 1;
//        cout << l << " " << r << endl;
        if (l <= 3 && 3 < r) {
//            cout << "hey :)" << endl;
        }
    };
    auto setWhite = [&](int l, int r) { //[l, r)
        lazyWhite[l] += 1;
        lazyWhite[r] -= 1;
    };

    for (int i = 0; i < n; ++i) {
        if (s[i] == 'X') {
            setBlack(i, i + 1);
        } else if (s[i] == '_') {
            setWhite(i, i + 1);
        }
    }

    vector last(k + 1, vector<int>(n + 1, -1)); //last good
    iota(last[0].begin(), last[0].begin() + nxtBlack[0], 0);
    fill(last[0].begin() + nxtBlack[0], last[0].end(), nxtBlack[0] - 1);
//    cout << "pref:\n";
    for (int i = 2; i < n - 2; ++i) {
        for (int j = 1; j <= k; ++j) {
            last[j][i] = last[j][i - 1];
            int L = i - c[j - 1] + 1;
            if (L >= 0 && canBlack(L, i + 1) && s[L - 1] != 'X') {
                int p = last[j - 1][L - 2];
                if (p != -1 && canWhite(p + 1, L)) {
                    pref[j][i] = true;
                    last[j][i] = i;
                }
            }
//            cout << pref[j][i] << " ";
        }
//        cout << endl;
    }
//    cout << endl;

    for (int i = 0; i <= k; ++i) {
        fill(last[i].begin(), last[i].end(), -1);
    }
    iota(last[k].begin() + prvBlack[n - 1] + 1, last[k].end(), prvBlack[n - 1] + 1);
    fill(last[k].begin(), last[k].begin() + prvBlack[n - 1] + 1, prvBlack[n - 1] + 1);

//    cout << "suf\n";
    for (int i = n - 3; i > 1; --i) {
        for (int j = 0; j < k; ++j) {
            last[j][i] = last[j][i + 1];
            int R = i + c[j];
            if (R <= n && canBlack(i, R) && s[R] != 'X') {
                int p = last[j + 1][R + 1];
                if (p != -1 && canWhite(R, p)) {
                    suf[j][i] = true;
                    last[j][i] = i;
                }
            }
//            cout << suf[j][i] << " ";
        }
//        cout << endl;
    }

    for (int j = 0; j < k; ++j) {
        vector<int> pntL(n);
        for (int i = 1; i < n; ++i) {
            auto goodL = [&]() {
                return pref[j][pntL[i]] && canWhite(pntL[i] + 1, i);
            };
            if (i + c[j] - 1 < n && pref[j + 1][i + c[j] - 1]) {
                pntL[i] = pntL[i - 1];
                while (pntL[i] < i - 1 && !goodL()) {
                    ++pntL[i];
                }
            }
        }
        vector<int> pntR(n, n - 1);
        for (int i = n - 2; i > 0; --i) {
            auto goodR = [&]() {
                return suf[j + 1][pntR[i]] && canWhite(i + c[j], pntR[i]);
            };
            if (i + c[j] - 1 < n && pref[j + 1][i + c[j] - 1] && suf[j][i]) {
                pntR[i] = pntR[i + 1];
                while (pntR[i] > i + c[j] - 1 && !goodR()) {
                    --pntR[i];
                }
                if (pntL[i] < i - 1 && pntR[i] < n) {
                    setBlack(i, i + c[j]);
                    setWhite(pntL[i] + 1, i);
                    setWhite(i + c[j], pntR[i]);
                }
            }
        }
    }

    string ans(n, '?');
    int sumWhite = 0, sumBlack = 0;
    for (int i = 0; i < n; ++i) {
        sumWhite += lazyWhite[i];
        sumBlack += lazyBlack[i];
        if (sumWhite && sumBlack) {
            ans[i] = '?';
        } else if (sumWhite) {
            ans[i] = '_';
        } else {
            assert(sumBlack);
            ans[i] = 'X';
        }
    }
    return ans.substr(2, n - 4);
}

• Subtask 1: 7 / 7
• Subtask 2: 3 / 3
• Subtask 3: 22 / 22
• Subtask 4: 27 / 27
• Subtask 5: 21 / 21
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10