Submission #591964

#	Time	Username	Problem	Language	Result	Execution time	Memory
591964		Vanilla	Paint By Numbers (IOI16_paint)	C++17	80 / 100	13 ms	2772 KiB

paint

#include <bits/stdc++.h>
#include "paint.h"
using namespace std;
const int maxn = 102;
bool dp[maxn][maxn][maxn]; // dp[i][j][k] -> is it possible to form an answer considering first i characters, first j blocks, and i being the k-th X of the j-th block

string solve_puzzle(string s, vector<int> c) {
    int n = s.size();
    int k = c.size();
    s.push_back('_');
    c.push_back(0);
    auto check = [&] () {
        memset(dp, 0, sizeof(dp));
        dp[0][0][0] = 1;
        for (int i = 1; i <= n + 1; i++){
            for (int j = 0; j <= k; j++){
                for (int ps = 0; ps <= c[j]; ps++){
                    char now = s[i-1];
                    if ((now == 'X' || now == '.') && ps) {
                        dp[i][j][ps] |= dp[i-1][j][ps - 1];
                    }
                    if ((now == '_' || now == '.') && !ps) {
                        if (j) dp[i][j][0]|=dp[i-1][j-1][c[j-1]];
                        dp[i][j][0]|=dp[i-1][j][0];
                    }
                    // if (dp[i][j][ps]) cout << i << " " << j << " " << ps << "\n";
                }
            }
        }
        return dp[n + 1][k][0];
    };
    string rs(n, '.');
    for (int i = 0; i < n; i++){
        if (s[i] != '.') rs[i]=s[i];
        else {
            s[i] = 'X';
            bool p1 = check();
            s[i] = '_';
            bool p2 = check();
            // cout << i << " " << p1 << " " << p2 << "\n";
            if (p1 && p2) rs[i]='?';
            else if (p1) rs[i]='X';
            else if (p2) rs[i]='_';
            s[i] = '.';
        }
    }
    return rs;
}

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