#include "paint.h"
#include <vector>
#include <iostream>
#include <cstdlib>
using namespace std;
void out(string s, const vector<pair<int,int>> &partitions, const vector<int> &pos, int k, const vector<int> &c)
{
return;
string out = s;
int curr = -1;
for (int i = 0; i < k; i++)
{
if (curr < partitions[pos[i]].first) curr = partitions[pos[i]].first;
else curr++;
for (int j = 0; j < c[i]; j++)
{
out[curr] = 'X';
curr++;
}
}
cout << out << "\n";
}
void evaluate(const vector<int> &positions, const vector<pair<int,int>> &partititions, const vector<int> &c, int pos, vector<pair<bool,bool>> &res)
{
vector<int> whites;
whites.push_back(partititions[pos].first - 1);
int curr = partititions[pos].first;
for (int i = 0; i < (int)positions.size(); i++)
{
if (positions[i] == pos)
{
whites.push_back(curr + c[i]);
curr += c[i] + 1;
}
}
int movedist = partititions[pos].second - whites.back();
curr = 0;
if (whites.size() == 1)
{
for (int i = partititions[pos].first; i < partititions[pos].second; i++)
{
res[i].second = true;
}
return;
}
if (movedist == 0)
{
int next = 1;
for (int i = partititions[pos].first; i < partititions[pos].second; i++)
{
if (next < (int)whites.size() && whites[next] == i)
{
next++;
res[i].second = true;
}
else
{
res[i].first = true;
}
}
return;
}
for (int i = partititions[pos].first; i < partititions[pos].second; i++)
{
if (curr < (int)whites.size() - 1 && i >= whites[curr + 1]) curr++;
res[i].first = true;
if (i <= whites[curr] + movedist)
{
res[i].second = true;
}
}
}
string solve_puzzle(string s, vector<int> c) {
int n = s.size();
int k = c.size();
vector<pair<int,int>> partitions;
vector<pair<bool,bool>> res(n, {false, false});
vector<int> space;
int lasts = 0;
for (int i = 0; i < n; i++)
{
if (s[i] == '_')
{
if (lasts != i)
{
partitions.push_back({lasts, i});
space.push_back(i - lasts + 1);
}
lasts = i + 1;
}
}
if (lasts != n)
{
partitions.push_back({lasts, n});
space.push_back(n - lasts + 1);
}
vector<int> pos(k, -1);
int p = partitions.size();
int curr = p - 1;
int i = k - 1;
while (curr >= 0 && i >= 0)
{
if (space[curr] < c[i] + 1)
{
curr--;
}
else
{
space[curr] -= c[i] + 1;
pos[i] = curr;
i--;
}
}
out(s, partitions, pos, k, c);
for (int i = 0; i < p; i++) evaluate(pos, partitions, c, i, res);
for (int i = 0; i < k; i++)
{
for (int next = pos[i] - 1; next >= 0; next--)
{
if (i > 0 && next < pos[i - 1]) break;
if (space[next] >= c[i] + 1)
{
int old = pos[i];
space[pos[i]] += c[i] + 1;
space[next] -= c[i] + 1;
pos[i] = next;
evaluate(pos, partitions, c, old, res);
evaluate(pos, partitions, c, next, res);
}
out(s, partitions, pos, k, c);
}
}
string ns;
for (int i = 0; i < n; i++)
{
if (s[i] != '.') ns.push_back(s[i]);
else
{
if (res[i].first && res[i].second) ns.push_back('?');
else if (res[i].first) ns.push_back('X');
else ns.push_back('_');
}
}
return ns;
}
