#include "paint.h"
#include <cstdlib>
#include <iostream>
#include <string>
std::string solve_puzzle(std::string str, std::vector<int> c) {
int k = c.size();
int n = str.size();
int prefix[200010] = { 0 }, suffix[200010] = { 0 };
if (str[0] == '_')
prefix[0] = 1;
if (str[n - 1] == '_')
suffix[n - 1] = 1;
for (int i = 1; i < n; ++i)
{
prefix[i] = prefix[i - 1];
if (str[i] == '_')
++prefix[i];
}
for (int i = n - 2; i >= 0; --i)
{
suffix[i] = suffix[i + 1];
if (str[i] == '_')
++suffix[i];
}
bool dp[200010][110] = { 0 }, dprev[200010][110] = { 0 };
bool flag = 1;
for (int i = 0; i < n; ++i)
{
if (str[i] == 'X')
flag = 0;
dp[i][0] = flag;
}
flag = 1;
for (int i = n - 1; i >= 0; --i)
{
if (str[i] == 'X')
flag = 0;
dprev[i][k] = flag;
}
dprev[n][k] = 1;
int sum = 0;
for (int i = 1; i <= k; ++i)
{
int howMuch = c[i - 1];
sum += howMuch;
if (i == 1)
{
if (prefix[howMuch - 1] == 0)
{
dp[howMuch - 1][i] = 1;
}
}
for (int j = sum; j < n; ++j)
{
if (str[j] != 'X')
{
dp[j][i] = dp[j - 1][i];
}
if (i == 1)
{
if (prefix[j] - prefix[j - howMuch] == 0)
dp[j][i] = std::max(dp[j][i], dp[j - howMuch][i - 1]);
continue;
}
if (prefix[j] - prefix[j - howMuch] == 0 && str[j - howMuch] != 'X')
{
dp[j][i] = std::max(dp[j][i], dp[j - howMuch - 1][i - 1]);
}
}
}
sum = 0;
for (int i = k - 1; i >= 0; --i)
{
int howMuch = c[i];
sum += howMuch;
if (i == k - 1)
{
if (suffix[n - howMuch] == 0)
{
dprev[n - howMuch][i] = 1;
}
}
for (int j = n - sum - 1; j >= 0; --j)
{
if (str[j] != 'X')
{
dprev[j][i] = dprev[j + 1][i];
}
if (i == k - 1)
{
if (suffix[j] - suffix[j + howMuch] == 0)
dprev[j][i] = std::max(dprev[j][i], dprev[j + howMuch][i + 1]);
continue;
}
if (suffix[j] - suffix[j + howMuch] == 0 && str[j + howMuch] != 'X')
{
dprev[j][i] = std::max(dprev[j][i], dprev[j + howMuch + 1][i + 1]);
}
}
}
int leftBiggest[200010][110] = { 0 };
int rightBiggest[200010][110] = { 0 };
int valq = 200005;
for (int i = k - 1; i >= 0; --i)
{
int biggest = valq;
if (i == k - 1)
biggest = n;
for (int j = n - 1; j >= 0; --j)
{
rightBiggest[j][i] = biggest;
if (dprev[j][i + 1] && biggest == valq)
biggest = j;
if (str[j] == 'X' && dprev[j][i + 1] != 1)
biggest = valq;
if (str[j] == 'X' && dprev[j][i + 1] == 1)
biggest = j;
}
}
for (int i = 1; i <= k; ++i)
{
int biggest = valq;
if (i == 1)
biggest = -1;
for (int j = 0; j < n; ++j)
{
leftBiggest[j][i] = biggest;
if (dp[j][i - 1] && biggest == valq)
biggest = j;
if (str[j] == 'X' && dp[j][i - 1] != 1)
biggest = valq;
if (str[j] == 'X' && dp[j][i - 1] == 1)
biggest = j;
}
}
/*
std::cout << "rightBiggest:\n";
for (int i = 0; i < k; ++i)
{
for (int j = 0; j < n; ++j)
{
std::cout << rightBiggest[j][i] << " ";
}
std::cout << "\n";
}
for (int j = 0; j < n; ++j)
{
leftBiggest[j][0] = -1;
rightBiggest[j][k] = n;
}
std::cout << "leftBiggest:\n";
for (int i = 1; i <= k; ++i)
{
for (int j = 0; j < n; ++j)
{
std::cout << leftBiggest[j][i] << " ";
}
std::cout << "\n";
}
std::cout << "DP:\n";
for (int i = 1; i <= k; ++i)
{
for (int j = 0; j < n; ++j)
{
std::cout << dp[j][i] << " ";
}
std::cout << "\n";
}
std::cout << "DPREV:\n";
for (int i = 0; i < k; ++i)
{
for (int j = 0; j < n; ++j)
{
std::cout << dprev[j][i] << " ";
}
std::cout << "\n";
}*/
int notx[200010] = { 0 }, xs[200010];
for (int i = 0; i < k; ++i)
{
int length = c[i];
if (length == n)
{
if (prefix[length - 1] == 0 && i == 0)
{
++xs[0];
--xs[length];
}
}
else
{
if (i == 0)
{
if (dprev[length + 1][i + 1] && prefix[length - 1] == 0 && str[length] != 'X')
{
++xs[0];
--xs[c[i]];
++notx[length];
--notx[rightBiggest[length][i]];
// std::cout << "RIGHT: " << length << " " << rightBiggest[length][i] << "\n";
}
}
if (i + 1 == k)
{
if (dp[n - length - 1][i] && suffix[n - length] == 0 && str[n - length - 1] != 'X')
{
++xs[n - length];
--xs[n];
++notx[leftBiggest[n - length][i + 1] + 1];
--notx[n - length];
// std::cout << "LEFT: " << leftBiggest[n - length][i + 1] + 1 << " " << n - length << "\n";
}
}
}
for (int j = c[i]; j < n - 1; ++j)
{
bool can = true;
if (str[j - length] == 'X' || str[j + 1] == 'X')
{
can = false;
continue;
}
if (j - length > 0)
{
if (dp[j - length - 1][i] == 0)
{
can = false;
continue;
}
}
if (j - length == 0 && i != 0)
{
can = false;
continue;
}
if (n - j >= 2)
{
if (dprev[j + 2][i + 1] == 0)
{
can = false;
continue;
}
}
if (prefix[j] - prefix[j - c[i]] > 0)
{
can = false;
continue;
}
if (can)
{/*
std::cout << i << " " << j << "|\n";
std::cout << "LEFT: " << leftBiggest[j - length + 1][i + 1] + 1 << " " << j - length + 1 << "\n";
std::cout << "RIGHT: " << j + 1 << " " << rightBiggest[j][i] << "\n";*/
++xs[j - length + 1];
--xs[j + 1];
++notx[leftBiggest[j - length + 1][i + 1] + 1];
--notx[j - length + 1];
++notx[j + 1];
--notx[rightBiggest[j][i]];
}
}
}
std::string ans = "";
int xsum = 0, notxsum = 0;
for (int i = 0; i < n; ++i)
{
// std::cout << xs[i] << " " << notx[i] << "\n";
xsum += xs[i];
notxsum += notx[i];
if (xsum > 0 && notxsum > 0)
ans += "?";
else if (xsum > 0)
ans += "X";
else
ans += "_";
}
return ans;
}
