#include "paint.h"
#include <bits/stdc++.h>
#include <cstdlib>
using namespace std;
int n,m,a[200005],dp[200005][105],rdp[200005][105],can[200005][2],p[200005];
char s[200005];
string otg;
void prec()
{
for(int i=1;i<=n;i++)
{
p[i]=p[i-1];
if(s[i]=='_')p[i]++;
}
}
void make_dp()
{
for(int i=1;i<=n;i++)
{
if(s[i]=='X')break;
dp[i][0]=1;
}
int last;
dp[0][0]=1;
for(int i=1;i<=m;i++)
{
last=0;
for(int j=1;j<=n;j++)
{
if(s[j]=='_')last=j;
if(s[j]=='_'||s[j]=='.')
{
dp[j][i]=dp[j-1][i];
}
if(s[j]=='X'||s[j]=='.')
{
if(last<=j-a[i])
{
if(i==1)dp[j][i]=max(dp[j][i],dp[j-a[i]][i-1]);
else dp[j][i]=max(dp[j][i],dp[j-a[i]-1][i-1]);
}
}
}
}
}
void make_rdp()
{
for(int i=n;i>=1;i--)
{
if(s[i]=='X')break;
rdp[i][m+1]=1;
}
rdp[n+1][m+1]=1;
int last;
for(int i=m;i>=1;i--)
{
last=n+1;
for(int j=n;j>=1;j--)
{
if(s[j]=='_')last=j;
if(s[j]=='_'||s[j]=='.')
{
rdp[j][i]=rdp[j+1][i];
}
if(s[j]=='X'||s[j]=='.')
{
if(last>=j+a[i])
{
if(i==m)rdp[j][i]=max(rdp[j][i],rdp[j+a[i]][i+1]);
else rdp[j][i]=max(rdp[j][i],rdp[j+a[i]+1][i+1]);
}
}
}
}
}
void resh()
{
int to=1;
s[0]='.';
for(int i=1;i<=n;i++)
{
if(s[i]=='_')
{
can[i][0]='_';
continue;
}
for(int j=0;j<=m;j++)
{
if(s[i]!='X'&&dp[i-1][j]&&rdp[i+1][j+1])
{
can[i][0]=1;
}
if(j==m)break;
if(j==0&&dp[i-1][j]&&rdp[i+a[j+1]+1][j+2]&&s[i-1]!='X'&&s[i+a[j+1]]!='X'&&p[i+a[j+1]-1]==p[i])
{
for(int z=max(to,i);z<i+a[j+1];z++)
{
can[z][1]=1;
}
to=max(to,i+a[j+1]);
}
if(j==m-1&&dp[i-2][j]&&rdp[i+a[j+1]][j+2]&&s[i-1]!='X'&&s[i+a[j+1]]!='X'&&p[i+a[j+1]-1]==p[i])
{
for(int z=max(to,i);z<i+a[j+1];z++)
{
can[z][1]=1;
}
to=max(to,i+a[j+1]);
}
if(dp[i-2][j]&&rdp[i+a[j+1]+1][j+2]&&s[i-1]!='X'&&s[i+a[j+1]]!='X'&&p[i+a[j+1]-1]==p[i])
{
for(int z=max(to,i);z<i+a[j+1];z++)
{
can[z][1]=1;
}
to=max(to,i+a[j+1]);
}
}
}
for(int i=1;i<=n;i++)
{
if(can[i][0]&&can[i][1])otg+='?';
else if(can[i][0])otg+='_';
else otg+='X';
}
}
string solve_puzzle(string S, vector<int> C)
{
n=S.size();
m=C.size();
for(int i=1;i<=n;i++)
{
s[i]=S[i-1];
}
for(int i=1;i<=m;i++)
{
a[i]=C[i-1];
}
prec();
make_dp();
make_rdp();
resh();
return otg;
}
Compilation message (stderr)
paint.h:1:9: warning: #pragma once in main file
1 | #pragma once
| ^~~~
paint_c.h:1:9: warning: #pragma once in main file
1 | #pragma once
| ^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |