Submission #639340

#	Time	Username	Problem	Language	Result	Execution time	Memory
639340		piOOE	Paint By Numbers (IOI16_paint)	C++17	59 / 100	1 ms	212 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, bool f = false) { //[l, r)
        if (!f) assert(l < r);
        return nxtBlack[l] >= r;
    };
    auto canBlack = [&](int l, int r, bool f = false) { //[l, r)
        if (!f) 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);
        }
    }

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

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

    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: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10