oj.uz

Submission #755252

# Submission time Handle Problem Language Result Execution time Memory
755252 2023-06-09T16:13:42 Z alexander707070 Paint By Numbers (IOI16_paint) C++14
59 / 100
 1 ms 340 KB 
#include <bits/stdc++.h>
using namespace std;

char s[200007];
vector<int> c;
string ans;

bool pref[200007][107],li[200007][107];
bool suff[200007][107],li2[200007][107];
bool white,black;
int sum[200007],n,k;

bool ff(int pos,int k){
    if(k==-1)return true;
    else if(pos<=0)return false;

    if(li[pos][k])return pref[pos][k];
    li[pos][k]=true;

    pref[pos][k]=ff(pos-1,k);
    if(pos>=c[k] and sum[pos]-sum[pos-c[k]]==0 and s[pos-c[k]]!='X' and ff(pos-c[k]-1,k-1)){
        pref[pos][k]=true;
    }

    return pref[pos][k];
}

bool ff2(int pos,int k){
    if(k==c.size())return true;
    else if(pos>=n+1)return false;

    if(li2[pos][k])return suff[pos][k];
    li2[pos][k]=true;

    suff[pos][k]=ff2(pos+1,k);
    if(pos+c[k]-1<=n and sum[pos+c[k]-1]-sum[pos-1]==0 and s[pos+c[k]]!='X' and ff2(pos+c[k]+1,k+1)){
        suff[pos][k]=true;
    }

    return suff[pos][k];
}

string solve_puzzle(string S, vector<int> C){
    c=C; n=int(S.size()); k=int(C.size());

    for(int i=1;i<=n;i++){
        s[i]=S[i-1]; sum[i]=sum[i-1];
        if(s[i]=='_')sum[i]++;
    }

    for(int i=1;i<=n;i++){
        if(s[i]!='.'){
            ans.push_back(s[i]); continue;
        }

        white=black=false;
        for(int f=-1;f<k;f++){
            if(ff(i-1,f) and ff2(i+1,f+1))white=true;
        }        
        
        for(int f=0;f<=k;f++){
            for(int t=max(i-c[f]+1,1);t<=i;t++){
                if(sum[t+c[f]-1]-sum[t-1]!=0 or s[t-1]=='X' or s[t+c[f]]=='X')continue;
                if(ff(t-2,f-1) and ff2(t+c[f]+1,f+1))black=true;
            }
        }

        if(white and black)ans.push_back('?');
        if(!white and black)ans.push_back('X');
        if(white and !black)ans.push_back('_');
    }

    return ans;
}

Compilation message

paint.cpp: In function 'bool ff2(int, int)':
paint.cpp:29:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     if(k==c.size())return true;
      |        ~^~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB n = 13, m = 1
2 Correct 1 ms 340 KB n = 18, m = 1
3 Correct 0 ms 340 KB n = 17, m = 1
4 Correct 0 ms 212 KB n = 1, m = 1
5 Correct 0 ms 340 KB n = 20, m = 1
6 Correct 1 ms 340 KB n = 20, m = 1
7 Correct 0 ms 340 KB n = 20, m = 1

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB n = 13, m = 1
2 Correct 1 ms 340 KB n = 18, m = 1
3 Correct 0 ms 340 KB n = 17, m = 1
4 Correct 0 ms 212 KB n = 1, m = 1
5 Correct 0 ms 340 KB n = 20, m = 1
6 Correct 1 ms 340 KB n = 20, m = 1
7 Correct 0 ms 340 KB n = 20, m = 1
8 Correct 0 ms 340 KB n = 20, m = 5
9 Correct 0 ms 340 KB n = 18, m = 3
10 Correct 1 ms 340 KB n = 17, m = 2
11 Correct 1 ms 340 KB n = 20, m = 2
12 Correct 0 ms 340 KB n = 17, m = 4
13 Correct 0 ms 340 KB n = 17, m = 6
14 Correct 0 ms 340 KB n = 17, m = 1
15 Correct 0 ms 340 KB n = 17, m = 4
16 Correct 1 ms 340 KB n = 13, m = 3
17 Correct 0 ms 340 KB n = 18, m = 4
18 Correct 0 ms 340 KB n = 20, m = 10
19 Correct 1 ms 340 KB n = 19, m = 10

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB n = 13, m = 1
2 Correct 1 ms 340 KB n = 18, m = 1
3 Correct 0 ms 340 KB n = 17, m = 1
4 Correct 0 ms 212 KB n = 1, m = 1
5 Correct 0 ms 340 KB n = 20, m = 1
6 Correct 1 ms 340 KB n = 20, m = 1
7 Correct 0 ms 340 KB n = 20, m = 1
8 Correct 0 ms 340 KB n = 20, m = 5
9 Correct 0 ms 340 KB n = 18, m = 3
10 Correct 1 ms 340 KB n = 17, m = 2
11 Correct 1 ms 340 KB n = 20, m = 2
12 Correct 0 ms 340 KB n = 17, m = 4
13 Correct 0 ms 340 KB n = 17, m = 6
14 Correct 0 ms 340 KB n = 17, m = 1
15 Correct 0 ms 340 KB n = 17, m = 4
16 Correct 1 ms 340 KB n = 13, m = 3
17 Correct 0 ms 340 KB n = 18, m = 4
18 Correct 0 ms 340 KB n = 20, m = 10
19 Correct 1 ms 340 KB n = 19, m = 10
20 Correct 1 ms 340 KB n = 100, m = 5
21 Correct 1 ms 340 KB n = 90, m = 3
22 Correct 1 ms 340 KB n = 86, m = 2
23 Correct 1 ms 340 KB n = 81, m = 4
24 Correct 1 ms 340 KB n = 89, m = 10
25 Correct 1 ms 340 KB n = 81, m = 23
26 Correct 1 ms 340 KB n = 86, m = 8
27 Correct 1 ms 340 KB n = 53, m = 22
28 Correct 1 ms 340 KB n = 89, m = 35
29 Correct 1 ms 340 KB n = 63, m = 25
30 Correct 1 ms 340 KB n = 100, m = 50
31 Correct 1 ms 340 KB n = 99, m = 50

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB n = 13, m = 1
2 Correct 1 ms 340 KB n = 18, m = 1
3 Correct 0 ms 340 KB n = 17, m = 1
4 Correct 0 ms 212 KB n = 1, m = 1
5 Correct 0 ms 340 KB n = 20, m = 1
6 Correct 1 ms 340 KB n = 20, m = 1
7 Correct 0 ms 340 KB n = 20, m = 1
8 Correct 0 ms 340 KB n = 20, m = 5
9 Correct 0 ms 340 KB n = 18, m = 3
10 Correct 1 ms 340 KB n = 17, m = 2
11 Correct 1 ms 340 KB n = 20, m = 2
12 Correct 0 ms 340 KB n = 17, m = 4
13 Correct 0 ms 340 KB n = 17, m = 6
14 Correct 0 ms 340 KB n = 17, m = 1
15 Correct 0 ms 340 KB n = 17, m = 4
16 Correct 1 ms 340 KB n = 13, m = 3
17 Correct 0 ms 340 KB n = 18, m = 4
18 Correct 0 ms 340 KB n = 20, m = 10
19 Correct 1 ms 340 KB n = 19, m = 10
20 Correct 1 ms 340 KB n = 100, m = 5
21 Correct 1 ms 340 KB n = 90, m = 3
22 Correct 1 ms 340 KB n = 86, m = 2
23 Correct 1 ms 340 KB n = 81, m = 4
24 Correct 1 ms 340 KB n = 89, m = 10
25 Correct 1 ms 340 KB n = 81, m = 23
26 Correct 1 ms 340 KB n = 86, m = 8
27 Correct 1 ms 340 KB n = 53, m = 22
28 Correct 1 ms 340 KB n = 89, m = 35
29 Correct 1 ms 340 KB n = 63, m = 25
30 Correct 1 ms 340 KB n = 100, m = 50
31 Correct 1 ms 340 KB n = 99, m = 50
32 Correct 0 ms 340 KB n = 13, m = 4
33 Correct 1 ms 340 KB n = 86, m = 2
34 Correct 1 ms 340 KB n = 88, m = 2
35 Correct 1 ms 340 KB n = 86, m = 2
36 Correct 1 ms 340 KB n = 81, m = 6
37 Correct 1 ms 340 KB n = 98, m = 7
38 Correct 1 ms 340 KB n = 92, m = 7
39 Correct 1 ms 340 KB n = 88, m = 21
40 Correct 1 ms 340 KB n = 90, m = 21
41 Correct 1 ms 340 KB n = 98, m = 22

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB n = 13, m = 1
2 Correct 1 ms 340 KB n = 18, m = 1
3 Correct 0 ms 340 KB n = 17, m = 1
4 Correct 0 ms 212 KB n = 1, m = 1
5 Correct 0 ms 340 KB n = 20, m = 1
6 Correct 1 ms 340 KB n = 20, m = 1
7 Correct 0 ms 340 KB n = 20, m = 1
8 Correct 0 ms 340 KB n = 20, m = 5
9 Correct 0 ms 340 KB n = 18, m = 3
10 Correct 1 ms 340 KB n = 17, m = 2
11 Correct 1 ms 340 KB n = 20, m = 2
12 Correct 0 ms 340 KB n = 17, m = 4
13 Correct 0 ms 340 KB n = 17, m = 6
14 Correct 0 ms 340 KB n = 17, m = 1
15 Correct 0 ms 340 KB n = 17, m = 4
16 Correct 1 ms 340 KB n = 13, m = 3
17 Correct 0 ms 340 KB n = 18, m = 4
18 Correct 0 ms 340 KB n = 20, m = 10
19 Correct 1 ms 340 KB n = 19, m = 10
20 Correct 1 ms 340 KB n = 100, m = 5
21 Correct 1 ms 340 KB n = 90, m = 3
22 Correct 1 ms 340 KB n = 86, m = 2
23 Correct 1 ms 340 KB n = 81, m = 4
24 Correct 1 ms 340 KB n = 89, m = 10
25 Correct 1 ms 340 KB n = 81, m = 23
26 Correct 1 ms 340 KB n = 86, m = 8
27 Correct 1 ms 340 KB n = 53, m = 22
28 Correct 1 ms 340 KB n = 89, m = 35
29 Correct 1 ms 340 KB n = 63, m = 25
30 Correct 1 ms 340 KB n = 100, m = 50
31 Correct 1 ms 340 KB n = 99, m = 50
32 Correct 0 ms 340 KB n = 13, m = 4
33 Correct 1 ms 340 KB n = 86, m = 2
34 Correct 1 ms 340 KB n = 88, m = 2
35 Correct 1 ms 340 KB n = 86, m = 2
36 Correct 1 ms 340 KB n = 81, m = 6
37 Correct 1 ms 340 KB n = 98, m = 7
38 Correct 1 ms 340 KB n = 92, m = 7
39 Correct 1 ms 340 KB n = 88, m = 21
40 Correct 1 ms 340 KB n = 90, m = 21
41 Correct 1 ms 340 KB n = 98, m = 22
42 Incorrect 1 ms 340 KB char #6 differ - expected: 'X', found: '?'
43 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB n = 13, m = 1
2 Correct 1 ms 340 KB n = 18, m = 1
3 Correct 0 ms 340 KB n = 17, m = 1
4 Correct 0 ms 212 KB n = 1, m = 1
5 Correct 0 ms 340 KB n = 20, m = 1
6 Correct 1 ms 340 KB n = 20, m = 1
7 Correct 0 ms 340 KB n = 20, m = 1
8 Correct 0 ms 340 KB n = 20, m = 5
9 Correct 0 ms 340 KB n = 18, m = 3
10 Correct 1 ms 340 KB n = 17, m = 2
11 Correct 1 ms 340 KB n = 20, m = 2
12 Correct 0 ms 340 KB n = 17, m = 4
13 Correct 0 ms 340 KB n = 17, m = 6
14 Correct 0 ms 340 KB n = 17, m = 1
15 Correct 0 ms 340 KB n = 17, m = 4
16 Correct 1 ms 340 KB n = 13, m = 3
17 Correct 0 ms 340 KB n = 18, m = 4
18 Correct 0 ms 340 KB n = 20, m = 10
19 Correct 1 ms 340 KB n = 19, m = 10
20 Correct 1 ms 340 KB n = 100, m = 5
21 Correct 1 ms 340 KB n = 90, m = 3
22 Correct 1 ms 340 KB n = 86, m = 2
23 Correct 1 ms 340 KB n = 81, m = 4
24 Correct 1 ms 340 KB n = 89, m = 10
25 Correct 1 ms 340 KB n = 81, m = 23
26 Correct 1 ms 340 KB n = 86, m = 8
27 Correct 1 ms 340 KB n = 53, m = 22
28 Correct 1 ms 340 KB n = 89, m = 35
29 Correct 1 ms 340 KB n = 63, m = 25
30 Correct 1 ms 340 KB n = 100, m = 50
31 Correct 1 ms 340 KB n = 99, m = 50
32 Correct 0 ms 340 KB n = 13, m = 4
33 Correct 1 ms 340 KB n = 86, m = 2
34 Correct 1 ms 340 KB n = 88, m = 2
35 Correct 1 ms 340 KB n = 86, m = 2
36 Correct 1 ms 340 KB n = 81, m = 6
37 Correct 1 ms 340 KB n = 98, m = 7
38 Correct 1 ms 340 KB n = 92, m = 7
39 Correct 1 ms 340 KB n = 88, m = 21
40 Correct 1 ms 340 KB n = 90, m = 21
41 Correct 1 ms 340 KB n = 98, m = 22
42 Incorrect 1 ms 340 KB char #6 differ - expected: 'X', found: '?'
43 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB n = 13, m = 1
2 Correct 1 ms 340 KB n = 18, m = 1
3 Correct 0 ms 340 KB n = 17, m = 1
4 Correct 0 ms 212 KB n = 1, m = 1
5 Correct 0 ms 340 KB n = 20, m = 1
6 Correct 1 ms 340 KB n = 20, m = 1
7 Correct 0 ms 340 KB n = 20, m = 1
8 Correct 0 ms 340 KB n = 20, m = 5
9 Correct 0 ms 340 KB n = 18, m = 3
10 Correct 1 ms 340 KB n = 17, m = 2
11 Correct 1 ms 340 KB n = 20, m = 2
12 Correct 0 ms 340 KB n = 17, m = 4
13 Correct 0 ms 340 KB n = 17, m = 6
14 Correct 0 ms 340 KB n = 17, m = 1
15 Correct 0 ms 340 KB n = 17, m = 4
16 Correct 1 ms 340 KB n = 13, m = 3
17 Correct 0 ms 340 KB n = 18, m = 4
18 Correct 0 ms 340 KB n = 20, m = 10
19 Correct 1 ms 340 KB n = 19, m = 10
20 Correct 1 ms 340 KB n = 100, m = 5
21 Correct 1 ms 340 KB n = 90, m = 3
22 Correct 1 ms 340 KB n = 86, m = 2
23 Correct 1 ms 340 KB n = 81, m = 4
24 Correct 1 ms 340 KB n = 89, m = 10
25 Correct 1 ms 340 KB n = 81, m = 23
26 Correct 1 ms 340 KB n = 86, m = 8
27 Correct 1 ms 340 KB n = 53, m = 22
28 Correct 1 ms 340 KB n = 89, m = 35
29 Correct 1 ms 340 KB n = 63, m = 25
30 Correct 1 ms 340 KB n = 100, m = 50
31 Correct 1 ms 340 KB n = 99, m = 50
32 Correct 0 ms 340 KB n = 13, m = 4
33 Correct 1 ms 340 KB n = 86, m = 2
34 Correct 1 ms 340 KB n = 88, m = 2
35 Correct 1 ms 340 KB n = 86, m = 2
36 Correct 1 ms 340 KB n = 81, m = 6
37 Correct 1 ms 340 KB n = 98, m = 7
38 Correct 1 ms 340 KB n = 92, m = 7
39 Correct 1 ms 340 KB n = 88, m = 21
40 Correct 1 ms 340 KB n = 90, m = 21
41 Correct 1 ms 340 KB n = 98, m = 22
42 Incorrect 1 ms 340 KB char #6 differ - expected: 'X', found: '?'
43 Halted 0 ms 0 KB -