Submission #74234

#	Time	Username	Problem	Language	Result	Execution time	Memory
74234		renatsj	Paint By Numbers (IOI16_paint)	C++14	32 / 100	2 ms	736 KiB

paint

#include "paint.h"
#include<bits/stdc++.h>
#include <cstdlib>
using namespace std;
int i,j,n,m,dp[300005][103],dp2[300005][103],prewhite[300005],preblack[300005],sufwhite[300005],sufblack[300005],canbewhite[300005],canbeblack[300005],liel1,liel2,liel;
list<int> x;
string solve_puzzle(string s, vector<int> c)
{
    n=s.size();
    m=c.size();
    i=1;
    while (i<=n)
    {
        prewhite[i]=prewhite[i-1];
        preblack[i]=preblack[i-1];
        if (s[i-1]=='X')
        {
            preblack[i]++;
        }
        if (s[i-1]=='_')
        {
            prewhite[i]++;
        }
        i++;
    }
    i=n;
    while (i>=1)
    {
        sufwhite[i]=sufwhite[i+1];
        sufblack[i]=sufblack[i+1];
        if (s[i-1]=='X')
        {
            sufblack[i]++;
        }
        if (s[i-1]=='_')
        {
            sufblack[i]++;
        }
        i--;
    }
    /*dp[0][0]=1;
    dp[0][1]=1;
    dp[0][2]=1;
    j=3;
    while (j<=n+2&&s[j-3]!='X')
    {
        dp[0][j]=1;
        j++;
    }
    dp2[0][n+1]=1;
    dp2[0][n]=1;
    dp2[0][n+2]=1;
    j=n-1;
    while (j>=0&&s[j]!='X')
    {
        dp2[0][j]=1;
        j++;
    }*/
    /*j=0;
    while (j<=n+2)
    {
        dp[0][j]=1;
        dp2[0][j]=1;
        j++;
    }*/
    j=0;
    while (j<=n+2)
    {
        //dp[0][j]=1;
        dp2[0][j]=1;
        j++;
    }
    dp[0][0]=1;
    dp[0][1]=1;
    dp[0][2]=1;
    j=3;
    while (j<=n+2&&s[j-3]!='X')
    {
        dp[0][j]=1;
        j++;
    }

    i=1;
    while (i<=m)
    {
        j=1;
        while (j<=n)
        {
            if (s[j-1]=='_')
            {
                dp[i][j]=dp[i][j-1];
            }
            else if (s[j-1]=='X')
            {
                if (prewhite[j]==prewhite[j-c[i-1]]&&j-c[i-1]-1>=0)
                {
                    if (i==1&&j-c[i-1]==0)
                    {
                        dp[i][j]=1;
                    }
                    else
                    {
                        dp[i][j]=dp[i-1][j-c[i-1]-1];
                    }
                }
            }
            else
            {
                if (i==1&&j-c[i-1]==0)
                {
                    dp[i][j]=1;
                }
                else if (j-c[i-1]<=0)
                {

                }
                else
                {
                    dp[i][j]=dp[i][j-1]||dp[i-1][j-c[i-1]-1];
                }
            }
            //cout << i << " " << j << " " << dp[i][j] << "\n";
            //cout << dp[i][j] << " ";
            j++;
        }
        //cout << "\n";
        i++;
    }
    for (int j:c)
    {
        x.push_front(j);
    }
    c.clear();
    for (int j:x)
    {
        c.push_back(j);
        //cout << j << " ";
    }
    x.clear();
    //cout << "\n";
    i=1;
    while (i<=m)
    {
        j=n;
        while (j>=1)
        {
            if (s[j-1]=='_')
            {
                dp2[i][j]=dp2[i][j+1];
            }
            else if (s[j-1]=='X')
            {
                if (sufwhite[j]==sufwhite[j+c[i-1]])
                {
                    dp2[i][j]=dp2[i-1][j+c[i-1]+1];
                }
            }
            else
            {
                dp2[i][j]=dp2[i][j+1]||dp2[i-1][j+c[i-1]+1];
            }
            //cout << i << " " << j << " " << dp2[i][j] << " " << c[i-1] << "\n";
            //cout << dp[i][j] << " ";
            j--;
        }
        //cout << "\n";
        i++;
    }
    i=1;
    while (i<=m)
    {
        j=1;
        while (j<=n)
        {
            //cout << dp2[i][j] << " ";
            j++;
        }
        //cout << "\n";
        i++;
    }
    j=1;
    while (j<=n)
    {
        if (s[j-1]=='.')
        {
            canbewhite[j]=1;
            canbeblack[j]=1;
        }
        else if (s[j-1]=='X')
        {
            canbeblack[j]=1;
            canbewhite[j]=0;
        }
        else
        {
            canbeblack[j]=0;
            canbewhite[j]=1;
        }
        i=0;
        while (i<=m)
        {
            if (dp[i][j-1]==1)
            {
                liel1=i;
            }
            if (dp2[i][j+1]==1)
            {
                liel2=i;
            }
            i++;
        }
        //cout << j << " " << liel1 << " " << liel2 << "\n";
        if (liel1+liel2<m)
        {
            canbewhite[j]=0;
        }
        if (canbewhite[j]==0&&canbeblack[j]==1)
        {
            s[j-1]='X';
        }
        if (canbewhite[j]==1&&canbeblack[j]==0)
        {
            s[j-1]='_';
        }
        j++;
    }
    i=1;
    while (i<=n)
    {
        prewhite[i]=prewhite[i-1];
        preblack[i]=preblack[i-1];
        if (s[i-1]=='X')
        {
            preblack[i]++;
        }
        if (s[i-1]=='_')
        {
            prewhite[i]++;
        }
        //cout << canbewhite[i] << " " << canbeblack[i] << "  " << prewhite[i] << " " << preblack[i] << "\n";
        i++;
    }
    for (int j:c)
    {
        x.push_front(j);
    }
    c.clear();
    for (int j:x)
    {
        c.push_back(j);
        //cout << j << " ";
    }
    liel=-1;
    j=1;
    while (j<=n)
    {
        i=0;
        while (i<m)
        {
            //cout << i << " " << j << " " << liel << "  ";
            //cout << j << " " << j+c[i]-1 << " " << s[j+c[i]-1] << " ";
            //cout << prewhite[j] << " " << prewhite[j+c[i]-1] << " ";
            //cout << dp[i][j-1] << " " << dp2[m-i][j+1] << "\n";
            if ((j==1||s[j-2]!='X')&&j+c[i]-1<=s.size()&&(s[j+c[i]-1]!='X')&&prewhite[j]==prewhite[j+c[i]-1]&&dp[i][j-1]==1&&dp2[m-i-1][j+1]==1)
            {
                liel=j+c[i]-1;
            }
            i++;
        }
        if (liel>=j)
        {
            canbeblack[j]=2;
        }
        j++;
    }
    string sss;
    j=1;
    while (j<=n)
    {
        if (canbeblack[j]==2&&canbewhite[j]==1)
        {
            sss+='?';
        }
        else if (canbeblack[j]==2)
        {
            sss+='X';
        }
        else
        {
            sss+='_';
        }
        //cout << canbeblack[j] << " " << canbewhite[j] << "\n";
        j++;
    }
    return sss;
}

Compilation message (stderr)

paint.cpp: In function 'std::__cxx11::string solve_puzzle(std::__cxx11::string, std::vector<int>)':
paint.cpp:264:46: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if ((j==1||s[j-2]!='X')&&j+c[i]-1<=s.size()&&(s[j+c[i]-1]!='X')&&prewhite[j]==prewhite[j+c[i]-1]&&dp[i][j-1]==1&&dp2[m-i-1][j+1]==1)
                                      ~~~~~~~~^~~~~~~~~~

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