Submission #1224651

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224651		LIA	Paint By Numbers (IOI16_paint)	C++17	59 / 100	3 ms	328 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

bool canSolve(const string &s, const vector<int> &c) {
    int n = s.size(), k = c.size();
    vector<vector<char>> dp(n+1, vector<char>(k+1,false));
    dp[0][0] = true;
    for (int i = 1; i <= n; ++i)
        dp[i][0] = dp[i-1][0] && s[i-1] != 'X';
    for (int j = 1; j <= k; ++j) {
        int len = c[j-1];
        for (int i = 1; i <= n; ++i) {
            if (s[i-1] != 'X' && dp[i-1][j])
                dp[i][j] = true;
            if (!dp[i][j] && i >= len) {
                bool ok = true;
                for (int t = i-len; t < i; ++t)
                    if (s[t] == '_') { ok = false; break; }
                if (ok) {
                    int prev = i - len - 1;
                    if (prev < 0) {
                        if (dp[0][j-1]) dp[i][j] = true;
                    } else if (s[prev] != 'X' && dp[prev][j-1]) {
                        dp[i][j] = true;
                    }
                }
            }
        }
    }
    return dp[n][k];
}

string solve_puzzle(string s, vector<int> c) {
    int n = s.size();
    string ans(n, '?');
    for (int i = 0; i < n; ++i) {
        if (s[i] == '_') {
            ans[i] = '_';
            continue;
        }
        string t = s;
        t[i] = '_';
        if (!canSolve(t, c)) {
            ans[i] = 'X';
            continue;
        }
        t[i] = 'X';
        if (!canSolve(t, c))
            ans[i] = '_';
    }
    return ans;
}

Compilation message (stderr)

paint.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
paint_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

• 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