Submission #1026778

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026778		boyliguanhan	Paint By Numbers (IOI16_paint)	C++17	100 / 100	242 ms	11468 KiB

paint

#include "paint.h"
#include<bits/stdc++.h>
using namespace std;
bitset<200100> tran1[101],tran2,ok[101],ok2[101],wht,blk;
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){
    return !blk[l];
}
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++)
        blk[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]);
        tran2[i]=noblk(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++){
        if(tran2[i])for(int j=0;j<=k;j++)
            wht[i]=wht[i]|ok[j][i]&ok[j][i+1];
        for(int j=0;j<k;j++){
            if(!ok[j][i])continue;  
            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(sumblk[i])
            str+='X';
        else str+='_';
    }
    return str;
}

Compilation message (stderr)

paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:45:35: warning: suggest parentheses around arithmetic in operand of '|' [-Wparentheses]
   45 |             wht[i]=wht[i]|ok[j][i]&ok[j][i+1];
      |                           ~~~~~~~~^~~~~~~~~~~

• 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