This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "paint.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define F first
#define S second
#define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
#define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) lli(x.size())
#define mp(i,a) make_pair(i,a)
#define pb(a) push_back(a)
#define bit(x,b) (x&(1LL<<b))
typedef long long int lli;
typedef pair <lli,lli> ii;
typedef pair <ii,lli> iii;
typedef vector <lli> vi;
int dp[2*10010][100],dp1[2*10010][100],pw[2*10010];
std::string solve_puzzle(std::string s, std::vector<int> c)
{
c.pb(0);
c.insert(c.begin(),0);
string s1=s;
s=" "+s;
int n=s.size()-2,k=c.size();
for(int i=0;i<n;++i)
s1[i]='?';
for(int i=2;i<=n+1;++i)
{
pw[i]=pw[i-1];
if(s[i]=='_')
pw[i]++;
}
for(int i=0;i<k;++i)
{
if(i==k-1)
dp[n+3][i]=1;
else
dp[n+3][i]=0;
if(i==k-1)
dp[n+2][i]=1;
else
dp[n+2][i]=0;
if(i==0)
dp1[0][i]=1;
else
dp1[0][i]=0;
if(i==0)
dp1[1][i]=1;
else
dp1[1][i]=0;
}
for(int i=n+1;i>=2;--i)
{
for(int j=k-1;j>=0;--j)
{
if(j==0)
{
dp[i][j]=dp[i][j+1];
continue;
}
if(s[i]!='X')
dp[i][j]=dp[i+1][j];
if(s[i]!='_'&&c[j]>0)
{
if(i+c[j]-1<=n+1&&pw[i+c[j]-1]-pw[i-1]==0&&(i+c[j]>n+1||s[i+c[j]]!='X'))
dp[i][j]=max(dp[i][j],dp[i+c[j]+1][j+1]);
}
}
}
for(int i=2;i<=n+1;++i)
{
for(int j=0;j<k;++j)
{
if(j==k-1)
{
dp1[i][j]=dp1[i][j-1];
continue;
}
if(s[i]!='X')
dp1[i][j]=dp1[i-1][j];
if(s[i]!='X'&&c[j]>0)
{
if(i-(c[j]-1)>=2&&pw[i]-pw[i-(c[j]-1)-1]==0&&(i-(c[j]-1)-1<2||s[i-(c[j]-1)-1]!='X'))
dp1[i][j]=max(dp1[i][j],dp1[i-(c[j]-1)-2][j-1]);
}
}
}
int re=0;
for(int i=2;i<=n+1;++i)
{
int fl=0,fl1=0;
for(int j=1;j<k;++j)
{
if(s[i]!='X'&&dp[i+1][j]+dp1[i-1][j-1]==2)
fl=1;
int in=i+c[j]-1;
if(s[i]!='_'&&j!=k-1&&in<=n+1&&pw[in]-pw[i-1]==0&&s[i-1]!='X'&&(in+1>n+1||s[in+1]!='X'))
{
if(dp1[i-2][j-1]+dp[in+2][j+1]==2)
{
fl1=1;
re=max(re,c[j]);
}
}
}
if(re>0)
{
fl1=1;
re--;
}
if(fl+fl1==2)
continue;
if(fl)
s1[i-2]='_';
else
s1[i-2]='X';
}
return s1;
}
# | 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... |