Submission #59256

#	Time	Username	Problem	Language	Result	Execution time	Memory
59256		Bodo171	Paint By Numbers (IOI16_paint)	C++14	100 / 100	485 ms	56744 KiB

paint

#include "paint.h"

#include <cstdlib>
#include <string>
#include <vector>
#include <iostream>
using namespace std;
string ans;
string ss;
vector<int> ww;
const int nmax=200005;
bool dp[105][nmax];
int mars[nmax],ok[nmax][2],sum[nmax],c[nmax];
bool viz[105][nmax];
int i,j,n,k,bl;
bool white(int poz)
{
    return (ss[poz]=='.'||ss[poz]=='_');
}
bool black(int st,int dr)
{
    return (sum[dr]-sum[st-1]==dr-st+1);
}
void dfs(int i,int j)
{
    if(i==0&&j==0)
        return;
    if(viz[i][j])
        return;
    viz[i][j]=1;
    if(dp[i][j-1]&&white(j))
    {
        ok[j][0]=1;
        dfs(i,j-1);
    }
    if(!i) return;
    int B=ww[i-1];
    if(i&&j>=B+1&&dp[i-1][j-B-1]&&white(j-B)&&black(j-B+1,j))
    {
        mars[j-B+1]++;
        mars[j+1]--;
        ok[j-B][0]=1;
        dfs(i-1,j-B-1);
    }
    if(i==1&&j==B&&black(1,B))
    {
        mars[j-B+1]++;
        mars[j+1]--;
        dfs(i-1,j-B);
    }
}
string solve_puzzle(string s, vector<int> c) {
    n=s.size();s="."+s;
    dp[0][0]=1;k=c.size();
    ss=s;
    for(i=0;i<c.size();i++)
        ww.push_back(c[i]);
    for(i=1;i<=n&&white(i);i++)
        dp[0][i]=1;
    for(i=1;i<=n;i++)
        sum[i]=sum[i-1]+(s[i]=='X'||s[i]=='.');
    for(i=1;i<=k;i++)
    {
        bl=c[i-1];
        if(i==1&&black(1,bl)) dp[i][bl]=1;
        for(j=bl+1;j<=n;j++)
        {
            dp[i][j]=((dp[i][j-1]&&white(j))||(dp[i-1][j-bl-1]&&black(j-bl+1,j)&&white(j-bl)));
        }
    }
    dfs(k,n);
    for(i=1;i<=n;i++)
    {
        mars[i]+=mars[i-1];
        ok[i][1]=(mars[i]!=0);
        if(ok[i][0]&&ok[i][1])
        {
            ans+='?';
        }
        else
        {
            if(ok[i][0]) ans+='_';
            else ans+='X';
        }
    }
    return ans;
}

Compilation message (stderr)

paint.cpp: In function 'std::__cxx11::string solve_puzzle(std::__cxx11::string, std::vector<int>)':
paint.cpp:56:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<c.size();i++)
             ~^~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 3 / 3
• Subtask 3: 22 / 22
• Subtask 4: 27 / 27
• Subtask 5: 21 / 21
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10