/**
* Nice little problem. O(nk) may work, so let's just do dp. Well, this problem
* mainly tests a contestant's fundamentals, e.g. things like prefix sum, dp,
* difference array, etc. Really tedious to code...
* If i met such problem in the real contest, i definitely cannot AC it. It just took
* me too long to code...
*
* Time Complexity: O(nk)
* Implementation 1
*/
#include <bits/stdc++.h>
#include "paint.h"
typedef std::vector<int> vec;
template<class T> struct Array2D {
T* values;
int _w;
Array2D(int h, int w) { values = new T[h * w], _w = w; }
~Array2D() { delete [] values; }
inline T* operator[](int x) { return values + x * _w; }
};
std::string solve_puzzle(std::string str, std::vector<int> c) {
int n = str.size(), seg = c.size();
vec prefix_b(n + 1), prefix_w(n + 1); // pre.sum. of black & w
prefix_b[0] = prefix_w[0] = 0;
for (int i = 1; i <= n; i++) {
prefix_b[i] = prefix_b[i - 1] + (str[i - 1] == 'X');
prefix_w[i] = prefix_w[i - 1] + (str[i - 1] == '_');
}
// dp1[i][s] = if it's possible for the first s segments end no later than the
// i-th position (but the first s+1 segments do not)
Array2D<bool> dp1(n + 1, seg + 1), dp2(n + 2, seg + 1); // fwd & back dir
dp1[0][0] = dp2[n + 1][0] = 1;
for (int s = 1; s <= seg; s++)
dp1[0][s] = 0, dp2[n + 1][s] = 0;
for (int i = 1; i <= n; i++) {
for (int s = 0; s <= seg; s++) {
dp1[i][s] = false;
dp1[i][s] |= (dp1[i - 1][s] && str[i - 1] != 'X');
if (s > 0 && i - c[s - 1] - (s > 1) >= 0) {
dp1[i][s] |= (dp1[i - c[s - 1] - (s > 1)][s - 1]
&& prefix_w[i] - prefix_w[i - c[s - 1]] == 0);
}
}
}
for (int i = n; i >= 1; i--) {
for (int s = 0; s <= seg; s++) {
dp2[i][s] = false;
dp2[i][s] |= (dp2[i + 1][s] && str[i - 1] != 'X');
if (s > 0 && i + c[seg - s] + (s > 1) <= n + 1) {
dp2[i][s] |= (dp2[i + c[seg - s] + (s > 1)][s - 1]
&& prefix_w[i + c[seg - s] - 1] - prefix_w[i - 1] == 0);
}
}
}
std::vector<bool> can_b(n), can_w(n);
for (int i = 1; i <= n; i++) {
can_w[i - 1] = false;
for (int l = 0; l <= seg && !can_w[i - 1] && str[i - 1] != 'X'; l++)
can_w[i - 1] = (str[i - 1] != 'X' && dp1[i - 1][l] && dp2[i + 1][seg - l]);
if (str[i - 1] == '_')
assert(can_w[i - 1]);
}
vec diff(n + 1, 0); // difference array for black
for (int i = 0; i < n; i++) {
for (int s = 0; s < seg; s++) {
if (i - c[s] + (s == 0) >= 0 && i + 2 + (s < seg - 1) <= n + 1
&& dp1[i - c[s] + (s == 0)][s] && dp2[i + 2 + (s < seg - 1)][seg - s - 1]
&& prefix_w[i + 1] - prefix_w[i - c[s] + 1] == 0) {
int l = i - c[s] + 1, r = i;
diff[l]++, diff[r + 1]--;
}
}
}
for (int i = 0, prefix_sum = 0; i < n; i++) {
prefix_sum += diff[i];
can_b[i] = (prefix_sum > 0);
assert(str[i] != '_' || !can_b[i]);
if (str[i] == 'X')
assert(can_b[i] && !can_w[i]);
}
std::string ans;
for (int i = 0; i < n; i++) {
assert(can_b[i] || can_w[i]);
if (can_b[i] && can_w[i])
ans.push_back('?');
else if (can_b[i])
ans.push_back('X');
else
ans.push_back('_');
}
return ans;
}
