oj.uz

Submission #889612

# Submission time Handle Problem Language Result Execution time Memory
889612 2023-12-20T03:52:59 Z Ghulam_Junaid Paint By Numbers (IOI16_paint) C++17
59 / 100
 1 ms 600 KB 
#include <bits/stdc++.h>
// #include "grader.cpp"
using namespace std;

const int N = 2e5 + 10;
const int K = 105;

int pref[N], suff[N];
int need_pref[K], need_suff[K];


// std::string solve_puzzle(std::string s, std::vector<int> c){
//     int n = s.length();
//     int k = c.size();

//     std::string ans = s;
//     int sz = c[0];
//     for (int i=0; i<n; i++)
//         ans[i] = '?';

//     int l = n - sz;
//     int r = sz - 1;
//     for (int i=l; i<=r; i++)
//         ans[i] = 'X';
//     return ans;
// }

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

    string ans = s;

    need_pref[0] = -2;
    for (int i=0; i<k; i++){
        int blacks = c[i];
        int available = 0;
        for (int j=need_pref[i] + 2; j<n; j++){
            available += (s[j] == '.');
            if (available == blacks){
                need_pref[i + 1] = j;
                break;
            }

            if (s[j] == '_')
                available = 0;
        }
    }

    for (int i=0; i<n; i++){
        for (int j=0; j<=k; j++){
            if (need_pref[j] > i)
                break;
            pref[i] = j;
        }
    }

    need_suff[k] = n + 1;
    for (int i=k - 1; i >= 0; i--){
        int blacks = c[i];
        int available = 0;
        for (int j=need_suff[i + 1] - 2; j >= 0; j--){
            available += (s[j] == '.');
            if (available == blacks){
                need_suff[i] = j;
                break;
            }

            if (s[j] == '_')
                available = 0;
        }
    }

    for (int i=n-1; i>=0; i--){
        for (int j=k; j>=0; j--){
            if (need_suff[j] < i)
                break;
            suff[i] = k - j;
        }
    }

    for (int i=0; i<n; i++){
        if (s[i] != '.') continue;

        // is this character always black or never black.

        // If I make it white, is the puzzle still solvable?
        bool can_be_white = 0;
        int put_in_pref = 0;
        for (int j=0; j<=k; j++){
            if (need_pref[j] >= i)
                break;
            put_in_pref = j;
        }
        can_be_white = (need_suff[put_in_pref] > i);

        if (!can_be_white){
            ans[i] = 'X';
            continue; 
        }

        bool can_be_black = 0;
        int l = i;
        int r = i;
        for (int j=i+1; j<n; j++){
            if (s[j] != '.')
                break;
            r++;
        }
        for (int j=i-1; j>=0; j--){
            if (s[j] != '.')
                break;
            l--;
        }

        for (int j=0; j<k; j++){
            for (int st = l; st <= i; st++){
                int en = st + c[j] - 1;
                if (en < i)
                    continue;
                if (en > r)
                    continue;

                if (need_pref[j] < (st - 1) && need_suff[j + 1] > (en + 1))
                    can_be_black = 1;
            }
        }

        if (can_be_black)
            ans[i] = '?';
        else
            ans[i] = '_';
    }

    return ans;
}

Subtask #1
7.0 / 7.0

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

Subtask #2
3.0 / 3.0

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

Subtask #3
22.0 / 22.0

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

Subtask #4
27.0 / 27.0

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

Subtask #5
0 / 21.0

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