Submission #1046949

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046949		yanb	Paint By Numbers (IOI16_paint)	C++14	100 / 100	351 ms	8684 KiB

paint

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

using namespace std;

vector<vector<bool>> gen_dp(string s, vector<int> c) {
    //cout << s << "\n";
    int n_cells = s.size(), n_blocks = c.size();
    vector<int> pref0(n_cells + 1), pref1(n_cells + 1);
    for (int i = 0; i < n_cells; i++) {
        pref0[i + 1] = pref0[i] + (s[i] == '_');
        pref1[i + 1] = pref1[i] + (s[i] == 'X');
    }

    vector<vector<bool>> dp(n_blocks + 1, vector<bool>(n_cells + 1));

    for (int i = 0; i <= n_cells; i++) {
        dp[0][i] = (pref1[i] == 0);
    }

    for (int i = 0; i < n_blocks; i++) {
        for (int j = 0; j < n_cells; j++) {
            if ((s[j] == 'X' || s[j] == '.') && j + 1 - c[i] >= 0 && pref0[j + 1] - pref0[j + 1 - c[i]] == 0 && s[j - c[i]] != 'X')
                dp[i + 1][j + 1] = dp[i][j - c[i]];
            if (s[j] == '_' || s[j] == '.') dp[i + 1][j + 1] = dp[i + 1][j + 1] || dp[i + 1][j];
        }
    }

    /*for (int i = 0; i <= n_blocks; i++) {
        for (int j = 0; j <= n_cells; j++) {
            cout << dp[i][j] << " ";
        }
        cout << "\n";
    }*/

    return dp;
}

string solve_puzzle(string s, vector<int> c) {
    s = "_" + s + "_";
    int n_cells = s.size(), n_blocks = c.size();
    vector<vector<bool>> dp = gen_dp(s, c);
    reverse(s.begin(), s.end());
    reverse(c.begin(), c.end());
    vector<vector<bool>> dpr = gen_dp(s, c);
    reverse(s.begin(), s.end());
    reverse(c.begin(), c.end());
    for (vector<bool> dprv : dpr) reverse(dprv.begin(), dprv.end());

    vector<int> pref0(n_cells + 1), pref1(n_cells + 1);
    for (int i = 0; i < n_cells; i++) {
        pref0[i + 1] = pref0[i] + (s[i] == '_');
        pref1[i + 1] = pref1[i] + (s[i] == 'X');
    }

    vector<bool> wok(n_cells), bok(n_cells);
    for (int i = 0; i < n_cells; i++) {
        if (s[i] != 'X') {
            for (int k = 0; k <= n_blocks; k++) {
                wok[i] = wok[i] || (dp[k][i] && dpr[n_blocks - k][n_cells - i - 1]);
            }
        }
    }

    for (int j = 0; j < n_blocks; j++) {
        vector<int> sok(n_cells);
        int len = c[j];
        for (int i = 1; i < n_cells - 1; i++) {
            if (s[i - 1] == 'X' || s[i + len] == 'X') continue;
            if (pref0[i + len] - pref0[i] != 0) continue;
            sok[i] = sok[i] || (dp[j][i - 1] && dpr[n_blocks - j - 1][n_cells - i - len - 1]);
        }
        
        int charge = 0;
        for (int i = 0; i < n_cells; i++) {
            if (sok[i]) charge = len;
            if (charge > 0) bok[i] = 1;
            charge--;
        }
    }

    string ans;
    for (int i = 1; i < n_cells - 1; i++) {
        if (bok[i] && wok[i]) ans += "?";
        else if (wok[i]) ans += "_";
        else if (bok[i]) ans += "X";
        else throw 1;
    }

    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