Submission #1037601

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037601		tengiz05	Paint By Numbers (IOI16_paint)	C++17	100 / 100	319 ms	175960 KiB

paint

#include "paint.h"

#include <cstdlib>
#include <iostream>

using namespace std;

std::string solve_puzzle(std::string s, std::vector<int> c) {
    int n = s.size();
    int k = c.size();
    
    string ans(n, '?');
    vector<int> W(n);
    
    vector sufdp(n + 1, vector<int>(k + 1, false));
    
    sufdp[n][k] = true;
    
    
    vector<int> preW(n + 1), updB(n + 1);
    for (int i = 0; i < n; i++) {
        preW[i + 1] = preW[i] + (s[i] == '_');
    }
    auto good = [&](int x, int len) {
        if (x + len <= n) {
            // for (int i = x; i < x + len; i++) {
                // if (s[i] == '_') {
                    // return false;
                // }
            // }
            if (preW[x + len] - preW[x] > 0) return false;
            if (x + len < n && s[x + len] == 'X') {
                return false;
            }
            return true;
        }
        return false;
    };
    
    auto update = [&](int l, int r) {
        // for (int i = l; i < r; i++) {
            // B[i]++;
        // }
        updB[l]++;
        updB[r]--;
        if (r < n) {
            W[r]++;
        }
    };
    
    for (int i = n - 1; i >= 0; i--) {
        for (int j = k; j >= 0; j--) {
            if (s[i] != 'X') {
                sufdp[i][j] |= sufdp[i + 1][j];
            }
            if (j < k && good(i, c[j])) {
                sufdp[i][j] |= sufdp[min(n, i + c[j] + 1)][j + 1];
            }
        }
    }
    
    
    
    vector predp(n + 1, vector<int>(k + 1, false));
    
    predp[0][0] = true;
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= k; j++) {
            if (!predp[i][j]) continue;
            if (s[i] != 'X') {
                predp[i + 1][j] |= predp[i][j];
                if (sufdp[i + 1][j]) {
                    W[i]++;
                }
            }
            if (j < k && good(i, c[j])) {
                predp[min(n, i + c[j] + 1)][j + 1] |= predp[i][j];
                if (sufdp[min(n, i + c[j] + 1)][j + 1]) {
                    // cout << i << " " << c[j] << "\n";
                    update(i, i + c[j]);
                }
            }
        }
    }
    
    for (int i = 1; i <= n; i++) {
        updB[i] += updB[i - 1];
    }
    
    for (int i = 0; i < n; i++) {
        if (W[i] && !updB[i]) {
            ans[i] = '_';
        }
        if (!W[i] && updB[i]) {
            ans[i] = 'X';
        }
    }
    
    return ans;
}

• 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