# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1192447 | simona1230 | Paint By Numbers (IOI16_paint) | C++20 | 0 ms | 584 KiB |
#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
int dp[200001][128][2];
int dp2[200001][128][2];
int b[200001];
int w[200001];
vector<int> pos[128];
int idx[128];
string solve_puzzle(string s, vector<int> c)
{
int minn=s.size(),maxx=-1;
int last=-1;
for(int i=0;i<s.size();i++)
{
if(s[i]=='_')last=i;
if(s[i]=='X')minn=min(minn,i),maxx=i;
for(int j=0;j<c.size();j++)
{
if(s[i]=='.'||s[i]=='X')
{
if(i+1>=c[j]&&last<=i-c[j])
{
if(j==0)dp[i][j][1]=1;
else dp[i][j][1]=dp[i-c[j]][j-1][0];
}
}
if(s[i]=='.'||s[i]=='_')
{
if(i!=0)
{
dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j][1]);
}
}
}
}
last=s.size();
for(int i=s.size();i>=0;i--)
{
if(s[i]=='_')last=i;
for(int j=c.size()-1;j>=0;j--)
{
if(s[i]=='.'||s[i]=='X')
{
if(s.size()-i>=c[j]&&last>=i+c[j])
{
if(j==c.size()-1)dp2[i][j][1]=1;
else dp2[i][j][1]=dp2[i+c[j]][j+1][0];
}
}
if(s[i]=='.'||s[i]=='_')
{
if(i!=s.size()-1)
{
dp2[i][j][0]=max(dp2[i+1][j][0],dp2[i+1][j][1]);
}
}
}
}
for(int i=0;i<s.size();i++)
{
for(int j=0;j<c.size();j++)
{
if(j<c.size()-1&&dp[i][j][0]&&dp2[i][j+1][0]||j==c.size()-1&&dp[i][j][0]&&maxx<i)w[i]=1;
if(dp[i][j][1]&&(j==c.size()-1||dp2[i+1][j+1][0]))pos[j].push_back(i);
//cout<<i<<" "<<j<<" "<<dp2[i][j][0]<<" "<<dp2[i][j][1]<<endl;
}
if(minn>i&&dp2[i][0][0])w[i]=1;
}
for(int i=0;i<s.size();i++)
{
for(int j=0;j<c.size();j++)
{
while(idx[j]<pos[j].size()&&pos[j][idx[j]]<i)idx[j]++;
if(idx[j]!=pos[j].size()&&pos[j][idx[j]]-c[j]+1<=i)b[i]=1;
}
}
string ans="";
for(int i=0;i<s.size();i++)
{
//cout<<i<<" "<<w[i]<<" "<<b[i]<<endl;
if(w[i]&&b[i])ans+='?';
else if(w[i])ans+='_';
else ans+='X';
}
return ans;
}
Compilation message (stderr)
# | 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... |