#include<bits/stdc++.h>
#include "paint.h"
using namespace std;
const int MAX_VAL=200*1000+5,MAX_BLOCS=100+5;
int nbVal,nbBlocs;
vector<int> listeBloc;
int etatDeb[MAX_VAL];
int prochBlanc[MAX_VAL];
int memo[MAX_VAL][MAX_BLOCS];
int possiBlanc[MAX_VAL],possiNoir[MAX_VAL];
string rep;
int dyna(int pos,int idBloc) {
if (pos>=nbVal) {
if (pos==nbVal and idBloc==nbBlocs) {
return 1;
}
else {
return 0;
}
}
if (memo[pos][idBloc]!=-1) {
return memo[pos][idBloc];
}
memo[pos][idBloc]=0;
int ans;
if (etatDeb[pos]!=1) {
ans=dyna(pos+1,idBloc);
if (ans==1) {
memo[pos][idBloc]=1;
possiBlanc[pos]=1;
}
}
if (idBloc<nbBlocs and pos+listeBloc[idBloc]-1<nbVal and prochBlanc[pos]>=pos+listeBloc[idBloc]
and (pos+listeBloc[idBloc]==nbVal or etatDeb[pos+listeBloc[idBloc]]!=1)) {
ans=dyna(min(pos+listeBloc[idBloc]+1,nbVal),idBloc+1);
if (ans==1) {
memo[pos][idBloc]=1;
possiNoir[pos]++;
possiNoir[pos+listeBloc[idBloc]]--;
possiBlanc[pos+listeBloc[idBloc]]++;
}
}
//cout<<pos<<" "<<idBloc<<" : "<<memo[pos][idBloc]<<endl;
return memo[pos][idBloc];
}
string solve_puzzle(string s,vector<int> c) {
nbVal=s.size();
listeBloc=c;
nbBlocs=listeBloc.size();
for (int i=0;i<nbVal;i++) {
if (s[i]=='.') {
etatDeb[i]=0;
}
if (s[i]=='X') {
etatDeb[i]=1;
}
if (s[i]=='_') {
etatDeb[i]=2;
}
//cout<<etatDeb[i]<<" ";
}
prochBlanc[nbVal]=nbVal;
for (int i=nbVal-1;i>=0;i--) {
prochBlanc[i]=prochBlanc[i+1];
if (etatDeb[i]==2) {
prochBlanc[i]=i;
}
}
for (int i=0;i<MAX_VAL;i++) {
for (int j=0;j<MAX_BLOCS;j++) {
memo[i][j]=-1;
}
}
dyna(0,0);
for (int i=1;i<nbVal;i++) {
possiNoir[i]+=possiNoir[i-1];
}
for (int i=0;i<nbVal;i++) {
//cout<<i<<" : "<<possiNoir[i]<<" "<<possiBlanc[i]<<endl;
if (etatDeb[i]!=0) {
rep+=s[i];
}
else {
if (possiBlanc[i]>0 and possiNoir[i]>0) {
rep+='?';
}
else if (possiBlanc[i]>0) {
rep+='_';
}
else if (possiNoir[i]>0) {
rep+='X';
}
}
}
return rep;
}
