Submission #1021825

#	Time	Username	Problem	Language	Result	Execution time	Memory
1021825		vjudge1	Paint By Numbers (IOI16_paint)	C++17	100 / 100	198 ms	45648 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>

using namespace std;

#define sz(s) (int)s.size()
#define pb push_back

const int MAX=2e5+10;

int n,k;
bool dpP[MAX][105],dpS[MAX][105];
int pX[MAX],pD[MAX];
int isX[MAX],isD[MAX];

int getD(int l,int r){
    if(l==0)return pD[r];
    return pD[r]-pD[l-1];
}

string solve_puzzle(string s, vector<int> c) {
    n=sz(s);
    k=sz(c);
    pX[0]=(s[0]=='X');
    pD[0]=(s[0]=='_');
    for(int i=1;i<n;i++){
        pX[i]=pX[i-1]+(s[i]=='X');
        pD[i]=pD[i-1]+(s[i]=='_');
    }
    dpS[n][k]=1;
    for(int i=n;i>0;i--){
        for(int j=k;j>=0;j--){
            if(s[i-1]!='X'){
                dpS[i-1][j]|=dpS[i][j];
            }
            if(j>0&&i-c[j-1]>=0&&getD(i-c[j-1],i-1)==0){
                if(j-1!=0){
                    if(i-c[j-1]-1>=0&&s[i-c[j-1]-1]!='X'){
                        dpS[i-c[j-1]-1][j-1]|=dpS[i][j];
                    }
                }
                else{
                    dpS[i-c[j-1]][j-1]|=dpS[i][j];
                }
            }
        }
    }
    {
        if(s[0]!='X'&&dpS[1][0]){
            isD[0]++;
            isD[1]--;
            dpP[0][0]=1;
        }
        if(getD(0,c[0]-1)==0&&dpS[c[0]][1]){
            if(k==1){
                isX[0]++;
                isX[c[0]]--;
                dpP[c[0]-1][1]=1;
            }
            else if(c[0]<n&&s[c[0]]!='X'){
                isD[c[0]]++;
                isD[c[0]+1]--;
                isX[0]++;
                isX[c[0]]--;
                dpP[c[0]][1]=1;
            }
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<=k;j++){
            if(dpP[i][j]==0)continue;
            if(i+1<n&&s[i+1]!='X'){
                bool ok=0;
                if(j==0){
                    if(dpS[i+2][j]){
                        ok=1;
                    }
                }
                else{
                    if(dpS[i+1][j]){
                        ok=1;
                    }
                }
                if(ok){
                    isD[i+1]++;
                    isD[i+2]--;
                    dpP[i+1][j]=1;
                }
            }
            if(j<k&&i+c[j]<n&&getD(i+1,i+c[j])==0&&dpS[i+c[j]+1][j+1]){
                if(j==k-1){
                    isX[i+1]++;
                    isX[i+c[j]+1]--;  
                    // cout<<i<<" "<<j<<" "<<i+c[j]<<" "<<j+1<<"\n";                  
                    dpP[i+c[j]][j+1]=1;
                }
                else if(i+c[j]+1<n&&s[i+c[j]+1]!='X'){
                    isD[i+c[j]+1]++;
                    isD[i+c[j]+2]--;
                    isX[i+1]++;
                    isX[i+c[j]+1]--;
                    dpP[i+c[j]+1][j+1]=1;
                }
            }
            // cout<<i<<" "<<j<<"\n";
        }
    }
    for(int i=1;i<n;i++){
        isX[i]+=isX[i-1];
        isD[i]+=isD[i-1];
    }
    string ans;
    for(int i=0;i<n;i++){
        if(s[i]!='.'){
            ans.pb(s[i]);
            continue;
        }
        if(isX[i]&&isD[i]){
            ans.pb('?');
        }
        else if(isX[i]){
            ans.pb('X');
        }
        else if(isD[i])ans.pb('_');
        else ans.pb('Q');
    }
    return ans;
}

• 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