#include <bits/stdc++.h>
#include "paint.h"
#include <cstdlib>
using namespace std;
std::string solve_puzzle(std::string v, std::vector<int> c) {
int N = v.size(); v.insert(v.begin(), '.');
int K = c.size(); c.insert(c.begin(), 0);
vector<bitset<102>> dpPref(N+1, 0), dpSuf(N+2, 0);
vector<int> sBranco(N+2);
for (int i = 1; i <= N; i++) sBranco[i] = sBranco[i-1] + (int)(v[i] == '_');
dpPref[0][0] = dpSuf[N+1][K+1] = 1;
for (int i = 1; i <= N; i++)
{
if (v[i] == 'X') {dpPref[i] = 0; continue;}
dpPref[i] = dpPref[i-1]; //i-1 tbm eh branco
for (int k = 1; k <= K; k++)
dpPref[i][k] = (dpPref[i][k] || ((i > c[k]) && (sBranco[i-1] - sBranco[i-c[k]-1] == 0) && dpPref[i-c[k]-1][k-1])); // i-1 eh preto da comp k
}
for (int i = N; i >= 1; i--)
{
if (v[i] == 'X') {dpSuf[i] = 0; continue;}
dpSuf[i] = dpSuf[i+1]; //i+1 tbm eh branco
for (int k = 1; k <= K; k++)
dpSuf[i][k] = (dpSuf[i][k] || ((i + c[k] <= N) && (sBranco[i + c[k]] - sBranco[i] == 0) && dpSuf[i+c[k]+1][k+1])); // i+1 eh preto da comp k
}
vector<int> poss(N+2); //qtd de poss de i ser preto
for (int k = 1; k <= K; k++)
for (int ini = 1, fim = c[k]; fim <= N; ini++, fim++)
{
if (sBranco[fim] - sBranco[ini-1] > 0) continue;
if (dpPref[ini-1][k-1] == 0) continue;
if (dpSuf[fim+1][k+1] == 0) continue;
poss[ini]++; poss[fim+1]--;
}
for (int i = 1; i <= N; i++) poss[i] += poss[i-1];
string resp;
for (int i = 1; i <= N; i++)
{
if (v[i] != '.') {resp += v[i]; continue;}
bool canBeWhite = 0;
for (int k = 0; k <= K; k++) canBeWhite = (canBeWhite || (dpPref[i][k] && dpSuf[i][k+1]));
bool canBeBlack = (poss[i] > 0);
if (canBeWhite && canBeBlack) resp += "?";
else if (canBeWhite) resp += "_";
else resp += "X";
}
return resp;
}
