#include "paint.h"
#include <cstdlib>
#include <iostream>
#define MAX_N 200000
#define MAX_K 100
int n, k;
std::string S;
std::vector<int> C;
int W[MAX_N], B[MAX_N];
bool memoLeft[MAX_N][MAX_K];
bool memoRight[MAX_N][MAX_K];
bool visLeft[MAX_N][MAX_K];
bool visRight[MAX_N][MAX_K];
bool possible[MAX_N][MAX_K];
int whiteInRange(int a, int b) {
int sum = W[b];
if (a)
sum -= W[a - 1];
return sum;
}
bool noBlacksInRange(int a, int b) {
int sum = B[b];
if (a)
sum -= B[a - 1];
return sum == 0;
}
bool canPlace(int i, int b) {
if (i < 0)
return false;
// white space before i
if (i > 0 && S[i - 1] == 'X')
return false;
// all black spaces
if (i + C[b] > n)
return false;
if (whiteInRange(i, i + C[b] - 1))
return false;
// white space after end of block
if (i <= n - 1 && S[i + C[b]] == 'X')
return false;
return true;
}
bool solLeft(int i, int b) {
if (i >= n)
return b == k;
if (b == k)
return noBlacksInRange(i, n - 1);
if (!visLeft[i][b]) {
visLeft[i][b] = true;
if (S[i] == '_') {
memoLeft[i][b] = solLeft(i + 1, b);
} else if (S[i] == 'X') {
memoLeft[i][b] = canPlace(i, b) && solLeft(i + C[b] + 1, b + 1);
} else {
memoLeft[i][b] = (solLeft(i + 1, b)) || (canPlace(i, b) && solLeft(i + C[b] + 1, b + 1));
}
}
return memoLeft[i][b];
}
bool solRight(int i, int b) {
if (i < 0)
return b == -1;
if (b == -1)
return noBlacksInRange(0, i);
if (!visRight[i][b]) {
visRight[i][b] = true;
if (S[i] == '_') {
memoRight[i][b] = solRight(i - 1, b);
} else if (S[i] == 'X') {
memoRight[i][b] = canPlace(i - C[b] + 1, b) && solRight(i - C[b] - 1, b - 1);
} else {
memoRight[i][b] = (solRight(i - 1, b)) || (canPlace(i - C[b] + 1, b) && solRight(i - C[b] - 1, b - 1));
}
}
return memoRight[i][b];
}
bool solutionWithBlock(int i, int b) {
if (!canPlace(i, b))
return false;
return (solRight(i - 2, b - 1) && solLeft(i + C[b] + 1, b + 1));
}
void fillPossiblePositionsForBlocks() {
for (int b = 0; b < k; b++) {
for (int i = 0; i < n; i++) {
if (solutionWithBlock(i, b)) {
for (int j = 0; j < C[b]; j++) {
possible[i + j][b] = true;
}
}
}
}
}
bool canBeWhite(int i) {
if (S[i] == 'X')
return false;
for (int b = -1; b < k; b++) {
if (solRight(i - 1, b) && solLeft(i + 1, b + 1))
return true;
}
return false;
}
bool canBeBlack(int i) {
if (S[i] == '_')
return false;
for (int b = 0; b < k; b++) {
if (possible[i][b])
return true;
}
return false;
}
std::string solve_puzzle(std::string s, std::vector<int> c) {
n = s.size();
k = c.size();
S = s;
C = c;
W[0] = S[0] == '_' ? 1 : 0;
B[0] = S[0] == 'X' ? 1 : 0;
for (int i = 1; i < n; i++) {
W[i] = W[i - 1];
W[i] += S[i] == '_' ? 1 : 0;
B[i] = B[i - 1];
B[i] += S[i] == 'X' ? 1 : 0;
}
fillPossiblePositionsForBlocks();
/*for (int i = 0; i < n; i++) {
for (int b = 0; b < k; b++) {
std::cout << possible[i][b] << " ";
}
std::cout << "\n";
}*/
// ans
std::string ans = s;
for (int i = 0; i < n; i++) {
if (!canBeWhite(i)) {
ans[i] = 'X';
continue;
}
if (canBeBlack(i)) {
ans[i] = '?';
} else {
ans[i] = '_';
}
}
return ans;
}
