제출 #1151083

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1151083		alexdd	Paint By Numbers (IOI16_paint)	C++20	80 / 100	2094 ms	1520 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
int n,k;
vector<vector<bool>> 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<bool>> dp(n+2,vector<bool>(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]=1;
        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]=1;
            if(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<bool>> prefdp = calc_dp(s,c);

    reverse(s.begin(),s.end());
    reverse(c.begin(),c.end());
    vector<vector<bool>> 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;

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

            /*s[i] = '_';
            auxdp = calc_dp(s,c);
            if(auxdp[n][k]) can_=1;*/

            s[i] = '.';

            for(int j=0;j<=k;j++)
                if(prefdp[i][j] && suffdp[n-(i+2)+1][k-j])
                    can_=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:
???___????


*/

컴파일 시 표준 에러 (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: 0 / 10
• Subtask 7: 0 / 10