#include "paint.h"
#include <cstdlib>
#include <vector>
#include <string>
#include <iostream>
#include <cassert>
using namespace std;
int N, K;
string S;
vector<int> C;
using VB = vector<bool>;
using VVB = vector<VB>;
const int MAXN = 200000;
const int MAXK = 100;
bool cached[MAXN][MAXK+1];
bool memo[MAXN][MAXK+1];
void reset_DP() {
for (int i = 0; i < N; i++)
for (int k = 0; k <= K; k++)
cached[i][k] = false;
}
bool dp(int n, int k) {
if (n >= N)
return k == K;
if (cached[n][k])
return memo[n][k];
bool res = false;
// start a block of C[k] black cells
if (k < K and n + C[k] <= N and S[n + C[k]] != 'X') {
bool ok = true;
for (int j = 0; j < C[k]; j++) {
if (S[n + j] == '_') {
ok = false;
break;
}
}
if (ok) {
res = res or dp(n + C[k] + 1, k+1);
}
}
// paint cell n white
if (S[n] != 'X') {
res = res or dp(n + 1, k);
}
cached[n][k] = true;
memo[n][k] = res;
return res;
}
std::string solve_puzzle(std::string s, std::vector<int> c) {
// cerr << s << endl;
N = s.size();
K = c.size();
S = s + "_";
C = c;
string res = s;
for (int i = 0; i < N; i++) {
if (S[i] == '.') {
S[i] = 'X';
reset_DP();
bool can_be_black = dp(0, 0);
S[i] = '_';
reset_DP();
bool can_be_white = dp(0, 0);
// cerr << "i: " << i << " " << can_be_black << " " << can_be_white << endl;
assert( can_be_black or can_be_white );
if (can_be_black and can_be_white)
res[i] = '?';
else if (can_be_black)
res[i] = 'X';
else
res[i] = '_';
S[i] = '.';
}
}
return res;
}
