Submission #1023096

#	Time	Username	Problem	Language	Result	Execution time	Memory
1023096		amirhoseinfar1385	Paint By Numbers (IOI16_paint)	C++17	100 / 100	313 ms	317652 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(i-c[j-1]-1>=0&&s[i-c[j-1]-1]=='X'){
                    continue;
                }
                if(s[i]=='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(s[i+c[j-1]-1]=='X'){
                    continue;
                }
                if(i>1&&s[i-2]=='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;
            }
            //cout<<i<<" "<<j<<" "<<dpps[i][j]<<" "<<dpsuf[i][j]<<endl;
            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&&s[i]!='X'){
                if(i-c[j-1]-1>=0&&s[i-c[j-1]-1]=='X'){
                    continue;
                }
                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(23);
        }
        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: 21 / 21
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10