#include "paint.h"
#include <numeric>
#include <deque>
#include <map>
#include <iostream>
using namespace std;
const string str_INVALID = "INVALID";
string add_strings(string s1, const string& s2){
const int& N = s1.size();
for(int i = 0; i < N; ++i){
char& c1 = s1[i];
const char& c2 = s2[i];
if(c1 != c2){
if(c1 == '?' || c2 == '?') c1 = '?';
if(c1 == '0') c1 = c2;
if((c1 == 'X' && c2 == '_')||
(c1 == '_' && c2 == 'X')) c1 = '?';
}
}
return s1;
}
int sum(const vector<int>& prefix_sum, const int& l, const int& r){
if(r < l ) return 0;
if(l == 0) return prefix_sum[r];
return prefix_sum[r] - prefix_sum[l-1];
}
string solve_AllClear(const int& N, const deque<int>& c){
const int& K = c.size();
vector<int> prefix_sum = vector<int>(K);
partial_sum(c.begin(), c.end(), prefix_sum.begin());
if(K != 0 && prefix_sum.back() + (K-1) > N) return str_INVALID;
string ret(N, '0');
for(int hint = 0; hint < K; ++hint){
int Left_left = sum(prefix_sum,0,hint-1) + hint;
int Right_right = N-1 - sum(prefix_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';
}
for(auto& i:ret) if(i == '0') i = '_';
return ret;
}
map<pair<string,deque<int>>, string> AMap;
string solvePart(const string& s, const deque<int>& c){
const int& K = c.size();
const int& N = s.size();
// cout << "s:" << s << endl;
string::size_type i = s.find('_');
if(i == string::npos){
string ret = solve_AllClear(s.size(), c);
return ret;
}else{
auto it = AMap.find(pair<string,deque<int>>(s, c));
if(it != AMap.end())
return it->second;
string::size_type j = i;
while(s[j] == '_') ++j;
const int& N1 = i;
string s2(s, j, string::npos);
// cout << "s2:" << s2 << endl;
deque<int> c1;
deque<int> c2(c);
string ret1(i, '0');
string ret_(j-i,'_');
string ret2(N-j, '0');
string ret(N, '0');
string newret;
for(int i = 0; i <= K; ++i){
ret1 = solve_AllClear(N1, c1);
// cout << "ret1:" << ret1 << endl;
ret2 = solvePart(s2, c2);
// cout << "ret2:" << ret2 << endl;
if(ret1 != str_INVALID && ret2 != str_INVALID){
newret = ret1+ret_+ret2;
ret = add_strings(ret, newret);
// cout << "ret:" << ret << endl;
}
if(i != K){
c1.push_back(c[i]);
c2.pop_front();
}
}
if(ret == string(N, '0')) ret = str_INVALID;
AMap[pair<string,deque<int>>(s, c)] = ret;
return ret;
// ret1 = solve_AllClear(s1);
}
}
string solve_puzzle(string s, vector<int> c){
/*
..........
2
3 4
=>??X???XX??
........
2
3 4
=>XXX_XXXX
..._._....
1
3
=>???___????
...................._.._..........__....................
6
5 5 5 5 5 5
...................._....................
5
5 5 5 5 5
............_............
5
3 3 3 3 3
_._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._.
4
1 1 1 1
=>_?_?_?_?_?_?_?_?_?_?_?_?_?_?_?_?_?_?_?_?_?_?_?_?_?_?_?_?_?_?_?_?_?_?_?_?_?_?_?_?_?_?_?_?_?_?_?_?_?_?
*/
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;
}
}
}
deque<int> cDqe(c.begin(),c.end());
// if(NoInfo == N){
// string ret = solve_AllClear(s.size(), cDqe);
// return ret;
// }else
if(Black == 0){
string ret = solvePart(s, cDqe);
return ret;
}
return "";
}
