#include "paint.h"
#include <bits/stdc++.h>
#include <cstdlib>
using namespace std;
using pii = pair<int, int>;
vector<vector<bool>> dp(std::string s, std::vector<int> c)
{
int n = s.size();
s = s+'_';
int k = c.size();
vector<int> whites(n+1, 0);
for (int i=1; i<=n; i++)
{
if (s[i-1]=='_')
whites[i] = whites[i-1]+1;
else
whites[i] = whites[i-1];
}
vector<vector<bool>> potential_index(n, vector<bool> (2*k+1, 0));
vector<int> painted(2*k+1, -1);
if (s[0]!='X')
potential_index[0][0] = 1;
if ((whites[0] == whites[c[0]]) and (s[c[0]]!='X'))
{
for (int i=0; i<c[0]; i++)
potential_index[i][1] = 1;
potential_index[c[0]][2] = 1;
}
//cout << "nakarating dito\n";
for (int curr = 1; curr<n; curr++)
{
//cout << "current index " << curr << '\n';
for (int pos = 0; pos <= (2*k); pos++)
{
//cout << "pos " << pos << '\n';
if ((pos%2)==0)
{
if (s[curr]!='X')
{
if (potential_index[curr-1][pos] == 1)
potential_index[curr][pos] = 1;
}
}
else
{
int streak_no = pos/2;
int streak = c[streak_no];
if ( (((curr+streak)<=n) and (whites[curr]==whites[curr+streak])) and ((potential_index[curr-1][pos-1]==1) and (s[curr+streak]!='X')) )
{
//cout << "checked in\n";
if ((curr+streak)<n)
potential_index[curr+streak][pos+1] = 1;
for (int i = max(painted[pos]+1, curr); i<(curr+streak); i++)
potential_index[i][pos] = 1;
painted[pos] = curr+streak-1;
}
}
}
}
return potential_index;
}
std::string solve_puzzle(std::string s, std::vector<int> c) {
vector<vector<bool>> a = dp(s, c);
int n = s.size();
int k = c.size();
/*for (int i=0; i<n; i++)
{
for (int j=0; j<=(2*k); j++)
cout << a[i][j] << ' ';
cout << '\n';
}*/
string ss;
for (int i=n-1; i>=0; i--)
ss.push_back(s[i]);
vector<int> cc;
for (int i = k-1; i>=0; i--)
cc.push_back(c[i]);
vector<vector<bool>> b = dp(ss, cc);
string ans;
for (int i=0; i<n; i++)
{
bool can_be_white = 0;
bool can_be_black = 0;
for (int j=0; j<=(2*k); j++)
{
if ((j%2) == 0)
{
if ((a[i][j]) and (b[n-1-i][2*k-j]))
can_be_white = 1;
}
else
{
if ((a[i][j]) and (b[n-1-i][2*k-j]))
can_be_black = 1;
}
}
if (can_be_white and can_be_black)
ans.push_back('?');
else if (can_be_white)
ans.push_back('_');
else if (can_be_black)
ans.push_back('X');
else
ans.push_back('o');
}
return ans;
}
