Submission #1151118

#	Time	Username	Problem	Language	Result	Execution time	Memory
1151118		alexdd	Paint By Numbers (IOI16_paint)	C++20	100 / 100	1094 ms	253116 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());

    s.push_back('#');

    vector<vector<int>> bune(k+2);
    for(int j=1;j<=k;j++)
    {
        for(int f=1;f<n;f++)
        {
            if(prefdp[f][j]==2 && s[f]!='X' && suffdp[n-f-1][k-j])
                bune[j].push_back(f);
        }
    }
    
    for(int i=0;i<n;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] = '.';*/



            if(n <= i+1 + c[k-1]-1 && prefdp[n][k]==2)
                canX=1;
            for(int j=1;j<=k;j++)
            {
                /*for(int f=i+1;f<=min(n-1,i+1+c[j-1]-1);f++)
                {
                    if(prefdp[f][j]==2 && s[f]!='X' && suffdp[n-f-1][k-j])
                        canX=1;
                }*/
                int poz = lower_bound(bune[j].begin(),bune[j].end(),i+1) - bune[j].begin();
                if(poz<bune[j].size() && bune[j][poz] <= i+1 + c[j-1]-1)
                    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: 27 / 27
• Subtask 5: 21 / 21
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10