Submission #1026407

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026407		vjudge1	Paint By Numbers (IOI16_paint)	C++17	32 / 100	2 ms	7868 KiB

paint

#include "paint.h"
#include<bits/stdc++.h>
using namespace std;
bitset<200100> tran1[101],tran2,ok[101],ok2[101],wht;
int sumblk[200100],prfblk[200100],prfwht[200100],n_;
inline int nowht(int l,int r){
    return r<=n_&&prfwht[r]==prfwht[l-1];
}
inline int noblk(int l,int r){
    return prfblk[r]==prfblk[l-1];
}
string solve_puzzle(string s, vector<int> c) {
    int n=s.size(),k=c.size();
    n_=n;
    s=" "+s;
    for(int i=1;i<=n;i++)
        prfblk[i]=s[i]=='X',prfwht[i]=s[i]=='_';
    for(int i=1;i<=n;i++)
        prfblk[i]+=prfblk[i-01],prfwht[i]+=prfwht[i-1];
    for(int i=1;i<=n;i++){
        for(int j=0;j<k;j++)
            tran1[j][i]=nowht(i,i+c[j]-1)&&noblk(i+c[j],i+c[j]);
        tran2[i]=noblk(i,i);
    }
    ok[0][1]=1;
    for(int i=1;i<=n;i++) {
        if(tran2[i])for(int j=0;j<=k;j++)
            ok[j][i+1]=ok[j][i+1]|ok[j][i];
        for(int j=0;j<k;j++)if(tran1[j][i]&&ok[j][i])
            ok[j+1][i+c[j]+1]=1;
    }
    ok2[k][n+1]=1;
    ok2[k][n+2]=1;
    for(int i=n+1;--i;){
        if(tran2[i])for(int j=0;j<=k;j++)
            ok2[j][i]=ok2[j][i+1]|ok2[j][i];
        for(int j=0;j<k;j++)
            if(tran1[j][i]&&ok2[j+1][i+c[j]+1])
                ok2[j][i]=1;
    }
    for(int i=0;i<=k;i++)
        ok[i]&=ok2[i];
    for(int i=1;i<=n;i++){
        for(int j=0;j<k;j++){
            if(!ok[j][i])continue;
            if(tran2[i]&&ok[j][i+1])wht[i]=1;
            if(tran1[j][i]&&ok[j+1][i+c[j]+1])
                sumblk[i]++,sumblk[i+c[j]]--,wht[i+c[j]]=1;
        }
    }
    string str;
    for(int i=1;i<=n;i++){
        sumblk[i]+=sumblk[i-1];
        if(wht[i]&&sumblk[i])
            str+='?';
        else if(wht[i])
            str+='_';
        else str+='X';
    }
    return str;
}

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