#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
| ^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |