#include "paint.h"
#include <bits/stdc++.h>
#include <cstdlib>
using namespace std;
std::string solve_puzzle(std::string s, std::vector<int> c) {
int n = s.size();
int k = c.size();
vector dpl(n + 5, vector(k + 5, vector<int>(2))), dpr(n + 5, vector(k + 5, vector<int>(2)));
vector<int> free(n + 5), black(n + 5, 0), white(n + 5, 0);
for(int i = 1; i <= n; i++){
free[i] += free[i - 1] + (s[i - 1] == '_');
}
// base case
dpl[0][0][0] = 1;
// dp[i][j][last] if we can place c[i]
for(int i = 0; i < n; i++){
for(int j = 0; j <= k; j++){
// place last == 0
int end = i + c[j] - 1;
if(end < n and free[end + 1] - free[i] == 0 and (end + 1 >= n or s[end + 1] != 'X')){
if(j < k){
dpl[end + 1][j + 1][1] |= dpl[i][j][0];
}
}
// do not place if last == 0 or 1
if(s[i] != 'X'){
dpl[i + 1][j][0] |= dpl[i][j][0] | dpl[i][j][1];
}
}
}
dpr[n][k][0] = 1;
for(int i = n; i >= 1; i--){
for(int j = k; j >= 0; j--){
// place last == 0
if(j > 0){
int end = i - c[j - 1] + 1;
if(end >= 1 and free[i] - free[end - 1] == 0 and (end - 2 < 0 or s[end - 2] != 'X')){
dpr[end - 1][j - 1][1] |= dpr[i][j][0];
//ans
if(dpl[end - 1][j - 1][0] & dpr[end - 1][j - 1][1]){
black[end - 1]++;
black[i + 1 - 1]--;
}
}
}
// do not place if last == 0 or 1
if(s[i - 1] != 'X'){
dpr[i - 1][j][0] |= dpr[i][j][0] | dpr[i][j][1];
// ans
white[i - 1] |= (dpl[i - 1][j][0] | dpl[i - 1][j][1]) & dpr[i - 1][j][0];
}
}
}
for(int i = 0; i < n; i++){
if(i > 0){
black[i] += black[i - 1];
}
if(black[i] and white[i]){
s[i] = '?';
}else if(black[i]){
s[i] = 'X';
}else if(white[i]){
s[i] = '_';
}
}
return s;
}
