#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> blocklengths;
string requirements;
vector<int> prefsumw;
vector<int> prefsumb;
vector<vector<bool>> dpl;
//[numblocks][ind] -- ending on white
//1-indexed!
vector<vector<bool>> dpr;
//0-indexed
int n,m;
// check whether block within a and b: prefsumw[b+1]-prefsum[a]==0
bool canFill(int a, int b){
return prefsumw[b+1]-prefsumw[a]==0;
}
bool canEmpty(int a, int b){
return prefsumb[b+1]-prefsumb[a]==0;
}
inline bool getL(int a, int x){
return dpl[a][x+1];
}
inline bool getR(int a, int x){
return dpr[a][x];
}
void gendata(){
n = requirements.size();
m = blocklengths.size();
//generate prefix sums
prefsumw.resize(n+1);
prefsumb.resize(n+1);
for (int i = 1; i<=n; i++){
prefsumw[i]=prefsumw[i-1]+(requirements[i-1]=='_');
prefsumb[i]=prefsumb[i-1]+(requirements[i-1]=='X');
}
//generate DP
dpl.resize(m+1,vector<bool>(n+1,false));
dpl[0][0]=true;
for (int a = 0; a<=m; a++){
for (int x = 1; x<=n; x++){
if (requirements[x-1]=='X'){
dpl[a][x]=false;
continue;
}
if (dpl[a][x-1]){
dpl[a][x]=true;
continue;
}
if (x-2>=0&&requirements[x-2]=='W'){
continue;
}
if (a>0&&x-1-blocklengths[a-1]>=0){
if (dpl[a-1][x-1-blocklengths[a-1]]){
dpl[a][x]=true;
continue;
}
}
}
}
dpr.resize(m+1,vector<bool>(n+1,false));
dpr[0][n]=true;
for (int a = 0; a<=m; a++){
for (int x = n-1; x>=0; x--){
if (requirements[x]=='X'){
dpr[a][x]=false;
continue;
}
if (dpr[a][x+1]){
dpr[a][x]=true;
continue;
}
if (x+1<n&&requirements[x+1]=='W'){
continue;
}
if (a>0&&x+1+blocklengths[m-a]<=n){
if (dpr[a-1][x+1+blocklengths[m-a]]){
dpr[a][x]=true;
continue;
}
}
}
}
/*for (int a = 0; a<=m; a++){
cout<<a<<" blocks to left:\n";
for (int i = 0; i<n; i++){
cout<<getL(a,i)<<' ';
}cout<<'\n';
}
for (int a = 0; a<=m; a++){
cout<<a<<" blocks to right:\n";
for (int i = 0; i<n; i++){
cout<<getR(a,i)<<' ';
}cout<<'\n';
}*/
}
std::string solve_puzzle(std::string s, std::vector<int> c) {
requirements = s;
blocklengths = c;
gendata();
vector<int> canUseBlack(n+1,0);
// what if a = 0
for (int a = 0; a<m; a++){
for (int x = 0; x+blocklengths[a]<=n; x++){
//can we place block a at x?
// possible off by one
if (getL(a,x-1)&&getR(m-1-a,x+blocklengths[a])&&canFill(x,x+blocklengths[a]-1)){
canUseBlack[x]++;
canUseBlack[x+blocklengths[a]]--;
//cout<<"can have block "<<a<<" from "<<x<<" to "<<x+blocklengths[a]-1<<'\n';
}
}
}
for (int i = 1; i<=n; i++){
canUseBlack[i]+=canUseBlack[i-1];
}
/*cout<<"can have black:\n";
for (int i = 0; i<n; i++){
cout<<bool(canUseBlack[i]>0)<<' ';
}cout<<'\n';*/
vector<bool> canUseWhite(n,false);
for (int a = 0; a<=m; a++){
for (int x = 0; x<n; x++){
if (getL(a,x)&&getR(m-a,x)){
canUseWhite[x]=true;
}
}
}
/*cout<<"can have white:\n";
for (int i = 0; i<n; i++){
cout<<canUseWhite[i]<<' ';
}cout<<'\n';*/
string answer;
for (int i = 0; i<n; i++){
if (canUseBlack[i]>0&&canUseWhite[i]){
answer+='?';
} else if (canUseBlack[i]>0){
answer+='X';
} else if (canUseWhite[i]){
answer+='_';
} else {
assert(1==0);
}
}
return answer;
}
