Submission #593072

#	Time	Username	Problem	Language	Result	Execution time	Memory
593072		alirezasamimi100	Paint By Numbers (IOI16_paint)	C++17	100 / 100	180 ms	47680 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10, K = 1e2 + 10;

int ps[2][N],sp[2][N];
bool dp[N][K],pd[N][K];
int get(int c, int l, int r){
    return ps[c][r]-ps[c][l-1];
}
string solve_puzzle(string s, vector<int> c) {
    int n=s.size(),k=c.size();
    s='#'+s;
    c.insert(c.begin(),0);
    for(int i=1; i<=n; i++){
        ps[0][i]=ps[0][i-1];
        ps[1][i]=ps[1][i-1];
        if(s[i]=='_') ps[0][i]++;
        if(s[i]=='X') ps[1][i]++;
    }
    dp[0][0]=1;
    pd[n+1][k+1]=1;
    for(int i=1; i<=n; i++){
        if(s[i]=='X') continue;
        for(int j=0; j<=k; j++){
            dp[i][j]=dp[i-1][j];
            if(j>0 && i>c[j] && get(0,i-c[j],i-1)==0) dp[i][j]|=dp[i-c[j]-1][j-1];
        }
    }
    for(int i=n; i; i--){
        if(s[i]=='X') continue;
        for(int j=k+1; j; j--){
            pd[i][j]=pd[i+1][j];
            if(j<=k && n-i>=c[j] && get(0,i+1,i+c[j])==0) pd[i][j]|=pd[i+c[j]+1][j+1];
        }
    }
    for(int i=1; i<=n; i++){
        for(int j=0; j<=k; j++){
            if(dp[i][j] && pd[i][j+1]) sp[0][i]=1;
            if(!j) continue;
            if(i>=c[j] && dp[i-c[j]][j-1] && pd[i+1][j+1] && get(0,i-c[j]+1,i)==0){
                sp[1][i-c[j]+1]++;
                sp[1][i+1]--;
            }
        }
    }
    string ans;
    for(int i=1; i<=n; i++){
        sp[1][i]+=sp[1][i-1];
        if(sp[1][i] && sp[0][i]) ans.push_back('?');
        else if(sp[1][i]) ans.push_back('X');
        else ans.push_back('_');
    }
    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