oj.uz

Submission #352339

# Submission time Handle Problem Language Result Execution time Memory
352339 2021-01-20T15:45:31 Z EndRay Paint By Numbers (IOI16_paint) C++17
32 / 100
 1 ms 492 KB 
#include "paint.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 2e5+2, logN = 18+1, K = 100+2;

string s;
int n, k;
bool dp[N][K], rdp[N][K];
bool can_black[N];

int fl[N];
bool table[logN][N];

void init(){
    fl[1] = 0;
    for(int i = 2; i < n; ++i)
        fl[i] = fl[i/2]+1;
    for(int i = 1; i < n; ++i)
        table[0][i] = (s[i] != '_');
    for(int d = 0; d < logN-1; ++d)
        for(int i = 1; i < n-(1<<(d+1))+1; ++i)
            table[d+1][i] = table[d][i] | table[d][i+(1<<d)];
}

int get(int l, int r){ /// [l, r)
    int level = fl[r-l];
    return table[level][l] | table[level][r-(1<<level)];
}

string solve_puzzle(string s, vector<int> c) {
    s = "#" + s;
    ::s = s;
    c.insert(c.begin(), -1);
    n = s.size();
    k = c.size();
    s = s + "#";
    init();
    dp[0][0] = true;
    for(int i = 1; i < n; ++i){
        dp[i][0] = (s[i] != 'X' && dp[i-1][0]);
        for(int j = 1; j < k; ++j)
            dp[i][j] |= (s[i] != '_' && i >= c[j] && (i == c[j] && j == 1 || i != c[j] && s[i-c[j]] != 'X' && dp[i-c[j]-1][j-1]) && get(i-c[j]+1, i+1)) || (s[i] != 'X' && dp[i-1][j]);
    }
    rdp[n][k] = true;
    for(int i = n-1; i >= 1; --i){
        rdp[i][k] = (s[i] != 'X' && rdp[i+1][k]);
        for(int j = k-1; j >= 1; --j)
            rdp[i][j] |= (s[i] != '_' && i <= n-c[j] && (i == n-c[j] && j == k-1 || i != n-c[j] && s[i+c[j]] != 'X' && rdp[i+c[j]+1][j+1]) && get(i, i+c[j])) || (s[i] != 'X' && rdp[i+1][j]);
    }
    for(int j = 1; j < k; ++j){
        int rest = 0;
        if(j == 1){
            int i = 1;
            if(get(i, i+c[j]) && s[i+c[j]] != 'X' && rdp[i+c[j]+1][j+1])
                rest = c[j];
            if(rest) can_black[i] = rest--;
        }
        for(int i = 2; i < n-c[j]; ++i){
            if(get(i, i+c[j]) && s[i-1] != 'X' && s[i+c[j]] != 'X' && dp[i-2][j-1] && rdp[i+c[j]+1][j+1])
                rest = c[j];
            if(rest) can_black[i] = rest--;
        }
        if(j == k-1){
            int i = n-c[j];
            if(get(i, i+c[j]) && s[i-1] != 'X' && dp[i-2][j-1])
                rest = c[j];
        }
        for(int i = n-c[j]; i < n; ++i)
            if(rest) can_black[i] = rest--;
    }
    string ans = s;
    for(int i = 1; i < n; ++i){
        if(ans[i] == '.'){
            bool can_white = false;
            for(int j = 0; j < k; ++j)
                if(dp[i-1][j] && rdp[i+1][j+1]){
                    can_white = true;
                    break;
                }
            if(!can_white) ans[i] = 'X';
            else if(!can_black[i]) ans[i] = '_';
            else ans[i] = '?';
        }
    }
    return ans.substr(1, n-1);
}

Compilation message

paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:44:65: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   44 |             dp[i][j] |= (s[i] != '_' && i >= c[j] && (i == c[j] && j == 1 || i != c[j] && s[i-c[j]] != 'X' && dp[i-c[j]-1][j-1]) && get(i-c[j]+1, i+1)) || (s[i] != 'X' && dp[i-1][j]);
      |                                                       ~~~~~~~~~~^~~~~~~~~
paint.cpp:50:70: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   50 |             rdp[i][j] |= (s[i] != '_' && i <= n-c[j] && (i == n-c[j] && j == k-1 || i != n-c[j] && s[i+c[j]] != 'X' && rdp[i+c[j]+1][j+1]) && get(i, i+c[j])) || (s[i] != 'X' && rdp[i+1][j]);
      |                                                          ~~~~~~~~~~~~^~~~~~~~~~~

Subtask #1
7.0 / 7.0

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

Subtask #2
3.0 / 3.0

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

Subtask #3
22.0 / 22.0

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

Subtask #4
0 / 27.0

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

Subtask #5
0 / 21.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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