Submission #1151103

#	Time	Username	Problem	Language	Result	Execution time	Memory
1151103		alexdd	Paint By Numbers (IOI16_paint)	C++20	32 / 100	0 ms	328 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
int n,k;
vector<vector<int>> calc_dp(string s, vector<int> cit_c)
{
    vector<int> c;
    c.push_back(0);
    for(int x:cit_c) c.push_back(x);
    s = "#" + s;

    vector<int> pref_(n+2,0);
    for(int i=1;i<=n;i++)
    {
        pref_[i] = pref_[i-1];
        if(s[i]=='_') pref_[i]++;
    }

    vector<vector<int>> dp(n+2,vector<int>(k+2,0));
    dp[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        if(dp[i-1][0] && s[i]!='X')
            dp[i][0]=1;
        if(i>=c[1] && pref_[i] - pref_[i-c[1]] == 0 && dp[i-c[1]][0])
            dp[i][1]=2;
        for(int j=1;j<=k;j++)
        {
            if(i-c[j]-1 < 0)
                continue;
            if(dp[i-c[j]-1][j-1] && s[i-c[j]]!='X' && pref_[i] - pref_[i-c[j]] == 0)
                dp[i][j]=2;
            if(dp[i][j]!=2 && dp[i-1][j] && s[i]!='X')
                dp[i][j]=1;
        }
    }
    return dp;
}
string solve_puzzle(string s, vector<int> c)
{
    n = s.size();
    k = c.size();
    assert(k>0);
    string rez = "";

    vector<vector<int>> prefdp = calc_dp(s,c);

    reverse(s.begin(),s.end());
    reverse(c.begin(),c.end());
    vector<vector<int>> suffdp = calc_dp(s,c);
    reverse(s.begin(),s.end());
    reverse(c.begin(),c.end());

    for(int i=0;i<s.size();i++)
    {
        if(s[i]=='.')
        {
            bool canX=0,can_=0;

            for(int j=0;j<=k;j++)
                if(prefdp[i][j] && suffdp[n-i-1][k-j])
                    can_=1;
            if(can_==0)
            {
                rez.push_back('X');
                continue;
            }

            /*s[i] = 'X';
            vector<vector<bool>> auxdp = calc_dp(s,c);
            if(auxdp[n][k]) canX=1;
            s[i] = '.';*/

            for(int j=1;j<=k;j++)
            {
                for(int f=i+1;f<=min(n,i+1+c[j-1]-1);f++)
                {
                    if(prefdp[f][j] && ((f==n && j==k) || (f<n && s[f]!='X' && suffdp[n-(f+2)+1][k-j])))
                        canX=1;
                }
            }



            assert(canX || can_);
            if(canX && can_)
                rez.push_back('?');
            else if(canX)
                rez.push_back('X');
            else
                rez.push_back('_');
        }
        else
            rez.push_back(s[i]);
    }
    return rez;
}
/*

..........
2 3 4


..._._....
1 3
output:
???___????


*/

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
      |         ^~~~

• 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