Submission #1040909

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040909		vjudge1	Paint By Numbers (IOI16_paint)	C++17	100 / 100	146 ms	81728 KiB

paint

#include "paint.h"

#include<bits/stdc++.h>
using namespace std;

std::string solve_puzzle(std::string s, std::vector<int> c) {
    int n=s.size();
    int k=c.size();
    bool dp[n+1][k+1][2];
    memset(dp,0,sizeof(dp));
    // dp0 == black
    // dp1 == white
    int lastwhite[n+1];
    lastwhite[0]=0;
    for(int i=1;i<=n;i++){
        lastwhite[i]=lastwhite[i-1];
        if(s[i-1]=='_'){
            lastwhite[i]=i;
        }
    }
    dp[0][0][1]=1;
    for(int i=1;i<=n;i++){
        char ch=s[i-1];
        if(ch!='X'){
            for(int j=0;j<=k;j++){
                dp[i][j][1]=dp[i-1][j][1]||dp[i-1][j][0];
            }
        }
        if(ch!='_'){
            for(int j=1;j<=k;j++){
                if(0<=i-c[j-1]&&lastwhite[i]<=i-c[j-1]){
                    dp[i][j][0]=dp[i-c[j-1]][j-1][1];
                }
            }
        }
    }
    bool up[n+1][k+1][2];
    memset(up,0,sizeof(dp));
    up[n][k][0]=up[n][k][1]=1;
    bool canblack[n+1]{},canwhite[n+1]{};
    int r=n+1,l=n+1;
    for(int i=n;i;i--){
        for(int j=0;j<=k;j++){
            if(dp[i][j][0]&&up[i][j][0]){
                if(i<l){
                    r=l=i;
                    canblack[i]=1;
                }
                while(i-c[j-1]+1<l){
                    canblack[--l]=1;
                }
                up[i-c[j-1]][j-1][1]=1;
            }
            if(dp[i][j][1]&&up[i][j][1]){
                canwhite[i]=1;
                up[i-1][j][0]=up[i-1][j][1]=1;
            }
        }
    }
    string ans;
    for(int i=1;i<=n;i++){
        if(canblack[i]){
            if(canwhite[i]){
                ans.push_back('?');
            }else{
                ans.push_back('X');
            }
        }else{
            ans.push_back('_');
        }
    }
    return ans;
}

Compilation message (stderr)

paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:41:9: warning: variable 'r' set but not used [-Wunused-but-set-variable]
   41 |     int r=n+1,l=n+1;
      |         ^

• 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