///http://ioi2016.ru/uploads/file_store/attached_file/26/paint.pdf
///https://oj.uz/problem/view/IOI16_paint
#include "paint.h"
#include <numeric>
#include <iostream>
using namespace std;
vector<int> prefix_sum;
int sum(const int& a, const int& b){
if(b < a ) return 0;
if(a == 0) return prefix_sum[b];
else return prefix_sum[b]-prefix_sum[a-1];
}
string solve_puzzle(string s, vector<int> c){
/*
..........
2
3 4
=>??X???XX??
........
2
3 4
=>XXX_XXXX
*/
const int& N = s.size();
const int& K = c.size();
int Black = 0, White = 0, NoInfo = 0;{
for(const auto& ch:s){
switch(ch){
case 'X': ++ Black; break;
case '_': ++ White; break;
case '.': ++NoInfo; break;
default : break;
}
}
}
prefix_sum = vector<int>(c.size());
partial_sum(c.begin(), c.end(), prefix_sum.begin());
if(NoInfo == N){
// if(N == sum(0,K-1)+(K-1)){
// string ret(s);
// int index = 0;
// for(int i = 0; i < K; ++i){
// for(int j = 0; j < c[i]; ++j, ++index){
// ret[index] = 'X';
// }
// if(i != K-1)
// ret[index++] = '_';
// }
// return ret;
// }else{
string ret(N, '0');
for(int hint = 0; hint < K; ++hint){
// cout << ret << endl;
int Left_left = sum(0,hint-1) + hint;
int Right_right = N-1 - sum(hint+1,K-1) - (K-hint-1);
int Right_left = Right_right - c[hint] + 1;
int Left_right = Left_left + c[hint] - 1;
for(int i = Left_left; i < Right_left; ++i)
ret[i] = '?';
for(int i = Left_right+1; i <= Right_right; ++i)
ret[i] = '?';
for(int i = Right_left; i <= Left_right; ++i)
if(ret[i] == '0')
ret[i] = 'X';
// switch(ret[i]){
// case '0': ret[i] = 'X';
// case '_': ret[i] = '?';
// default: break;
// }
}
for(auto& i:ret)
if(i == '0')
i = '_';
// cout << endl;
return ret;
// }
}
return "";
}
