#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
string S;
vector<int> C;
bool can_substring_be_black(int l, int r) {
if (r >= (int) S.size())
return false;
if (l-1 >= 0 and S[l-1] == 'X')
return false;
for (int j = l; j <= r; j++) {
if (S[j] == '_')
return false;
}
if (r+1 < (int) S.size() and S[r+1] == 'X')
return false;
return true;
}
const int MAXN = 5000;
const int MAXK = 100;
bool cached[MAXN+1][MAXK+1];
bool memo[MAXN+1][MAXK+1];
// dp(i, k) = true si es posible llenar el substring S[i .. N-1]
// y que cumpla con las condiciones de C[k], C[k+1], ...
bool dp( int i, int k ) {
if (i >= (int) S.size()) {
if (k == (int) C.size())
return true;
else
return false;
}
if (cached[i][k])
return memo[i][k];
bool res = false;
if (S[i] == '_') {
res = dp(i + 1, k);
}
else if (S[i] == 'X') {
// las proximas C[k] celdas deben ser negros
if (k < (int) C.size()) {
bool ok = can_substring_be_black(i, i + C[k] - 1);
if (ok) {
res = dp( i + C[k] + 1, k+1 );
}
}
}
else { // S[i] == '.'
// intentamos pintar S[i] de negro
if (k < (int) C.size()) {
bool ok = can_substring_be_black(i, i + C[k] - 1);
if (ok) {
res = dp( i + C[k] + 1, k+1 );
}
}
if (!res) {
// intentamos pintar S[i] de blanco
res = dp(i + 1, k);
}
}
cached[i][k] = true;
memo[i][k] = res;
return res;
}
std::string solve_puzzle(std::string s, std::vector<int> c) {
S = s;
C = c;
string res(s.size(), '?');
for (int i = 0; i < (int) s.size(); i++) { // O(N)
if (s[i] == '.') {
// forzar s[i] a que sea negro
S[i] = 'X';
for (int i = 0; i <= (int) s.size(); i++)
for (int k = 0; k <= (int) c.size(); k++)
cached[i][k] = false;
bool can_be_black = dp( 0, 0 );
// forzar s[i] a que sea blanco
S[i] = '_';
for (int i = 0; i <= (int) s.size(); i++)
for (int k = 0; k <= (int) c.size(); k++)
cached[i][k] = false;
bool can_be_white = dp( 0, 0 );
if (can_be_black and can_be_white)
res[i] = '?';
else if (can_be_black)
res[i] = 'X';
else if (can_be_white)
res[i] = '_';
else // no debemos llegar a este else
assert( false );
S[i] = '.';
}
else
res[i] = s[i];
}
return res;
}
