#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
int N, Q;
enum INFO {ON, OFF, BOTH};
vector<INFO> info; // NOTE: 1-idx
// NOTE: blocks: 1-idx
vector<int> prefOff; // NOTE: exc
vector<vector<bool>> prefDP, suffDP; // NOTE: [exc][exc]
vector<int> diffOn, diffOff; // NOTE: [l, r) updates
int cntOff (int l, int r) {
return prefOff[r+1] - prefOff[l];
}
std::string solve_puzzle(std::string specified, std::vector<int> blocks) {
N = (int)specified.size();
Q = (int)blocks.size();
info.assign(N+20, BOTH);
for (int i = 0; i < N; i++) {
if (specified[i] == 'X') {
info[i+1] = ON;
}
else if (specified[i] == '_') {
info[i+1] = OFF;
}
else {
info[i+1] = BOTH;
}
}
// cerr << "info: ";
// for (int i = 1; i <= N; i++) cerr << info[i] << " ";
// cerr << "\n";
vector<int> tempBlocks(Q+20);
for (int q = 0; q < Q; q++) {
tempBlocks[q+1] = blocks[q];
}
swap(blocks, tempBlocks);
prefOff.assign(N+20, 0);
for (int i = 1; i <= N; i++) {
prefOff[i+1] = prefOff[i] + (info[i] == OFF);
}
// cerr << "prefOff: ";
// for (int i = 1; i <= N; i++) cerr << prefOff[i] << " ";
// cerr << "\n";
prefDP.assign(N+20, vector<bool>(Q+20, false));
prefDP[1][1] = true;
for (int i = 1; i <= N; i++) {
for (int q = 1; q <= Q+1; q++) {
if (prefDP[i][q]) {
if (info[i] != ON) {
prefDP[i+1][q] = true;
}
if (q <= Q) {
int blockOn = blocks[q];
// NOTE: [i, i + blockOn - 1]: ON, [i + blockOn, i + blockOn]: OFF
if (i + blockOn - 1 <= N && cntOff(i, i + blockOn - 1) == 0 && info[i + blockOn] != ON) {
prefDP[i + blockOn + 1][q+1] = true;
}
}
}
}
}
suffDP.assign(N+20, vector<bool>(Q+20, false));
suffDP[N][Q] = true;
suffDP[N+1][Q] = true;
for (int i = N; i >= 1; i--) {
for (int q = Q; q >= 0; q--) {
if (suffDP[i][q]) {
if (info[i] != ON) {
suffDP[i-1][q] = true;
}
int blockOn = blocks[q];
// NOTE: [i - blockOn + 1, i]: ON
if (q >= 1 && i == N && cntOff(i - blockOn + 1, i) == 0) {
suffDP[i - blockOn][q-1] = true;
}
// NOTE: [i - blockOn, i - 1]: ON, [i, i]: OFF
if (q >= 1 && 1 <= i - blockOn && cntOff(i - blockOn, i - 1) == 0 && info[i] != ON) {
suffDP[i - blockOn - 1][q-1] = true;
}
}
}
}
cerr << "prefDP tests:\n";
cerr << " exp: 1, got: " << prefDP[8][2] << "\n";
cerr << "suffDP tests:\n";
cerr << " exp: 1, got: " << suffDP[1][0] << "\n";
diffOn.assign(N+20, 0);
diffOff.assign(N+20, 0);
cerr << "inters:\n";
for (int i = 1; i <= N; i++) {
for (int q = 1; q <= Q+1; q++) {
// NOTE: [i, i]: OFF
if (prefDP[i][q] && info[i] != ON && suffDP[i][q-1]) {
// cerr << " " << i << " " << q << "\n";
diffOff[i]++, diffOff[i+1]--;
}
if (q <= Q) {
int blockOn = blocks[q];
// NOTE: [i, i + blockOn - 1]: ON, [i + blockOn, i + blockOn]: OFF
if (prefDP[i][q] && i + blockOn - 1 <= N && cntOff(i, i + blockOn - 1) == 0 && info[i + blockOn] != ON && suffDP[i + blockOn][q]) {
// cerr << " " << i << " " << i + blockOn - 1 << "\n";
diffOn[i]++, diffOn[i + blockOn]--;
diffOff[i + blockOn]++, diffOff[i + blockOn + 1]--;
}
}
}
}
for (int i = 1; i <= N; i++) {
diffOn[i+1] += diffOn[i];
diffOff[i+1] += diffOff[i];
if (info[i] == ON) diffOn[i] = 1;
if (info[i] == OFF) diffOff[i] = 1;
}
cerr << "diffOn: ";
for (int d : diffOn) cerr << d << " ";
cerr << "\ndiffOff: ";
for (int d : diffOff) cerr << d << " ";
cerr << "\n";
string ans;
for (int i = 1; i <= N; i++) {
if (diffOn[i] && diffOff[i]) {
ans += '?';
}
else if (diffOn[i] && !diffOff[i]) {
ans += 'X';
}
else if (!diffOn[i] && diffOff[i]) {
ans += '_';
}
else { // shouldnt happen
assert(false);
}
}
return ans;
}
