| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1302778 | Mamikonm1 | Paint By Numbers (IOI16_paint) | C++17 | 0 ms | 0 KiB |
//#include "paint.h"
#include <bits//stdc++.h>
const int S_MAX_LEN = 200 * 1000;
char buf[S_MAX_LEN + 1];
using namespace std;
#define V vector
#define pb push_back
const int N=200;
std::string solve_puzzle(std::string s, std::vector<int> c) {
int n=s.size(),k=c.size();
V<bitset<N+1>>dp1(n),dp2(n);
dp1[0][0]=1;
dp2[n-1][0]=1;
V<int> mek(n);
string ans;
bool d,de,zro;
for(int i=0;i<n;++i){
if(i)dp1[i]|=dp1[i-1];
if(i and s[i-1]=='X')continue;
for(int j=0;j<k;++j){
d=0;
if(i<2)d=!j;
else d=dp1[i-2][j];
if(i+c[j]-1>=n or !d)continue;
if(i+c[j]<n and s[i+c[j]]=='X')continue;
dp1[i+c[j]-1][j+1]=1;
}
}
for(int i=n-1;i>=0;--i){
if(i+1<n)dp2[i]|=dp2[i+1];
if(i+1<n and s[i+1]=='X')continue;
for(int j=0;j<k;++j){
d=0;
if(i+2>=n)d=!j;
else d=dp2[i+2][j];
if(i-c[k-j-1]+1<0 or !d)continue;
if(i-c[k-j-1]>=0 and s[i-c[k-j-1]]=='X')continue;
dp2[i-c[k-j-1]+1][j+1]=1;
de=0;
if(i-c[k-j-1]-1<0)de=!(k-j-1);
else de=dp1[i-c[k-j-1]-1][k-j-1];
if(de){
mek[i-c[k-j-1]+1]++;
if(i+1<n)mek[i+1]--;
}
}
}
for(int i=0;i<n;++i){
if(s[i]!='.'){
ans.pb(s[i]);
continue;
}
if(i)mek[i]+=mek[i-1];
zro=0;
for(int j=0;j<=k;++j){
d=de=0;
if(!i)d=!j;
else d=dp1[i-1][j];
if(i==n-1)de=!(k-j);
else de=dp2[i+1][k-j];
if(d and de){
zro=1;
break;
}
}
if(zro and mek[i])ans.pb('?');
else if(zro)ans.pb('_');
else ans.pb('X');
assert(zro or mek[i]);
}
return ans;
}
int main() {
assert(1 == scanf("%s", buf));
std::string s = buf;
int c_len;
assert(1 == scanf("%d", &c_len));
std::vector<int> c(c_len);
for (int i = 0; i < c_len; i++) {
assert(1 == scanf("%d", &c[i]));
}
std::string ans = solve_puzzle(s, c);
printf("%s\n", ans.data());
return 0;
}