Submission #1026778

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
1026778	2024-07-18 11:00:47	boyliguanhan	Paint By Numbers (IOI16_paint)	C++17	100 / 100	242 ms	11468 KiB

paint

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#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;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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