제출 #1036967

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1036967		aaaaaarroz	Paint By Numbers (IOI16_paint)	C++17	59 / 100	1 ms	4696 KiB

paint

    #include "paint.h"
    #include<bits/stdc++.h>
    using namespace std;
    const int maxn=200000+10,maxk=200;
    int n,k,dpps[maxn][maxk],dpsuf[maxn][maxk],vas[maxn],ted1[maxn],ted2[maxn],hey[maxn];
     
    std::string solve_puzzle(std::string s, std::vector<int> c) {
        n=(int)s.size();
        k=(int)c.size();
        s.push_back('.');
        for(int i=1;i<=n;i++){
            ted1[i]+=ted1[i-1];
            ted2[i]+=ted2[i-1];
            ted1[i]+=(s[i-1]=='X');
            ted2[i]+=(s[i-1]=='_');
        }
        dpps[0][0]=1;
        dpsuf[n+1][k+1]=dpsuf[n+2][k+1]=1;
        for(int i=1;i<=n;i++){
            if(s[i-1]!='X'){
                dpps[i][0]|=dpps[i-1][0];
            }
            for(int j=1;j<=k;j++){
                if(s[i-1]!='X'){
                    dpps[i][j]|=dpps[i-1][j];
                }
                if(i>=c[j-1]+(j>1)&&ted2[i]-ted2[i-c[j-1]]==0){
                    if(j>0&&s[i-c[j-1]-1]=='X'){
                        continue;
                    }
                    dpps[i][j]|=dpps[i-c[j-1]-(j>1)][j-1];
                }
            }
        }
          for(int i=n;i>=1;i--){
            if(s[i-1]!='X'){
                dpsuf[i][k+1]|=dpsuf[i+1][k+1];
            }
            for(int j=k;j>=1;j--){
                if(s[i-1]!='X'){
                    dpsuf[i][j]|=dpsuf[i+1][j];
                }
                if(i+c[j-1]+(j<k)-1<=n&&ted2[i+c[j-1]-1]-ted2[i-1]==0){
                    if(j<k&&s[i+c[j-1]-1]=='X'){
                        continue;
                    }
                    dpsuf[i][j]|=dpsuf[i+c[j-1]+(j<k)][j+1];
                }
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=0;j<=k;j++){
                if(dpps[i-1][j]==1&&dpsuf[i+1][j+1]==1){
                    vas[i]=1;
                }
                if(dpps[i][j]==1&&dpsuf[i+2][j+1]==1&&j>0&&dpps[i-c[j-1]-(j>1)][j-1]==1&&ted2[i]-ted2[i-c[j-1]]==0){
                    hey[i]++;
                    hey[i-c[j-1]]--;
                }
            }
        }
        for(int i=n;i>=0;i--){
            hey[i]+=hey[i+1];
            if(hey[i]!=0){
                vas[i]+=2;
            }
        }
        string ret;
        ret.resize(n);
        for(int i=0;i<n;i++){
            if(s[i]=='X'||s[i]=='_'){
                ret[i]=s[i];
                continue;
            }
            if(vas[i+1]==0){
                exit(0);
            }
            if(vas[i+1]==1){
                ret[i]='_';
            }else if(vas[i+1]==2){
                ret[i]='X';
            }else{
                ret[i]='?';
            }
        }
        return ret;
    }

• Subtask 1: 7 / 7
• Subtask 2: 3 / 3
• Subtask 3: 22 / 22
• Subtask 4: 27 / 27
• Subtask 5: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10