#include "paint.h"
#include <iostream>
#include <vector>
#include <string>
using namespace std;
string solve_puzzle(string s, vector<int> c)
{
int n = s.size();
int k = c.size();
int W[n+1], B[n+1];
W[0] = B[0] = 0;
for(int i = 1; i <= n; i++)
{
W[i] = W[i-1];
B[i] = B[i-1];
if(s[i-1] == 'X') B[i]++;
else if(s[i-1] == '_') W[i]++;
}
int cover_pref[n+1][k+1]; //can the first i positions accomodate the first j blocks
cover_pref[0][0] = 1;
for(int j = 1; j <= k; j++) cover_pref[0][j] = 0;
for(int i = 1; i <= n; i++)
{
cover_pref[i][0] = (B[i] == 0);
for(int j = 1; j <= k; j++)
{
cover_pref[i][j] = 0;
cover_pref[i][j] |= (B[i] - B[i-1] == 0) && cover_pref[i-1][j];
cover_pref[i][j] |= (j == 1) && (i == c[j-1]) && (W[i] == 0);
cover_pref[i][j] |= (i > c[j-1])
&& (W[i] - W[i-c[j-1]] == 0)
&& (B[i-c[j-1]] - B[i-c[j-1]-1] == 0)
&& cover_pref[i - c[j-1] - 1][j-1];
}
}
vector<int> max_pref(n+2, 0);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= k; j++)
if(cover_pref[i][j])
max_pref[i] = max(max_pref[i], j);
max_pref[n+1] = max_pref[n];
int cover_suff[n+2][k+2]; //can the suffix starting from i accomodate j last j blocks
cover_suff[n+1][0] = 1;
for(int j = 1; j <= k; j++) cover_suff[n+1][j] = 0;
// cerr << n+1 << '\n';
// cerr << cover_suff[11][2] << '\n';
for(int i = n; i >= 1; i--)
{
cover_suff[i][0] = (B[n] - B[i-1] == 0);
// cerr << cover_suff[i][0] << ' ';
for(int j = 1; j <= k; j++)
{
cover_suff[i][j] = 0;
// cerr << i << ' ' << j << cover_suff[i+1][j];
cover_suff[i][j] |= (B[i] - B[i-1] == 0) && cover_suff[i+1][j];
// cerr << cover_suff[i][j] << '|';
cover_suff[i][j] |= (j == 1) && (i + c[k-j] - 1 == n) && (W[n] - W[i-1] == 0);
// cerr << cover_suff[i][j] << '|';
cover_suff[i][j] |= (i + c[k-j] - 1 < n)
&& (W[i + c[k-j] - 1] - W[i-1] == 0)
&& (B[i + c[k-j]] - B[i + c[k-j] - 1] == 0)
&& cover_suff[i + c[k-j] + 1][j-1];
// cerr << cover_suff[i][j] << ' ';
}
// cerr << '\n';
}
vector<int> max_suff(n+2, 0);
for(int i = n; i >= 1; i--)
for(int j = 1; j <= k; j++)
if(cover_suff[i][j])
max_suff[i] = max(max_suff[i], j);
max_suff[0] = max_suff[1];
vector<int> canbeWhite(n+1, 0);
for(int i = 1; i <= n; i++)
{
if(B[i] - B[i-1] != 0) continue;
for(int j = 0; j <= k; j++)
if(cover_pref[i-1][j] && cover_suff[i+1][k-j])
canbeWhite[i] = 1;
}
vector<int> ptr(n+1, 0);
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= k; j++)
{
// cerr << '\n';
// cerr << i << ' ' << j << '\n';
// cerr << 'A';
if(W[i + c[j-1] - 1] > W[i-1]) continue;
// cerr << 'B';
if(B[i-1] > B[max(0, i-2)]) continue;
// cerr << 'C';
if(i+c[j-1]-1 < n && B[i+c[j-1]] > B[i+c[j-1]-1]) continue;
// cerr << 'D';
if(i > 1 && !cover_pref[i-2][j-1]) continue;
// cerr << 'E';
if(!cover_suff[i + c[j-1] + 1][k-j]) continue;
// cerr << 'F';
ptr[i] = max(ptr[i], i + c[j-1] - 1);
}
}
// cerr << '\n';
// for(int i = 1; i <= n; i++)
// cerr << ptr[i] << ' ';
// cerr << '\n';
vector<int> canbeBlack(n+1, 0);
int p = 0;
for(int i = 1; i <= n; i++)
{
p = max(p, ptr[i]);
if(i <= p)
canbeBlack[i] = 1;
}
// for(int i = 1; i <= n; i++) cerr << canbeWhite[i] << ' ';
// cerr << '\n';
// for(int i = 1; i <= n; i++) cerr << canbeBlack[i] << ' ';
// cerr << '\n';
string res;
for(int i = 1; i <= n; i++)
{
if(canbeBlack[i] && canbeWhite[i]) res.push_back('?');
else if(canbeBlack[i]) res.push_back('X');
else res.push_back('_');
}
return res;
}
