oj.uz

Submission #1071757

# Submission time Handle Problem Language Result Execution time Memory
1071757 2024-08-23T10:55:15 Z TheQuantiX Paint By Numbers (IOI16_paint) C++17
59 / 100
 2 ms 604 KB 
#include <bits/stdc++.h>
#include "paint.h"

using namespace std;
using ll = long long;

constexpr ll MOD = 1000000007;

ll n, m, q, k, x, y, a, b, c;

vector< vector<ll> > do_dp(string &s, vector<int> &c) {
    vector< vector<ll> > dp1(m + 1, vector<ll> (n + 1));
    vector<ll> vec(1, 0);
    for (int i = 0; i < n; i++) {
        if (s[i] == '_') {
            vec.push_back(i + 1);
        }
    }
    vector<ll> vec2(1, 0);
    for (int i = 0; i < n; i++) {
        if (s[i] == 'X') {
            vec2.push_back(i + 1);
        }
    }
    for (int j = 0; j <= m; j++) {
        for (int i = 0; i <= n; i++) {
            if (j == 0) {
                dp1[j][i] = ((i == 0 || (vec2.size() == 1 || vec2[1] > i)) ? 1 : 0);
                // cout << dp1[j][i] << '\n';
                continue;
            }
            if (i == 0) {
                dp1[j][i] = 0;
                continue;
            }
            if (i >= c[j - 1] && i - vec[(upper_bound(vec.begin(), vec.end(), i) - vec.begin()) - 1] >= c[j - 1] && (i <= c[j - 1] + 1 || s[i - c[j - 1] - 1] != 'X') && (i == n || s[i] != 'X')) {
                if (j == 1) {
                    dp1[j][i] = ((vec2.size() == 1 || vec2[1] > i - c[j - 1]) ? 1 : 0);
                    // cout << j << ' ' << i << ' ' << vec2[1] << ' ' << i - c[j - 1] << '\n';
                }
                if (j > 1 && i >= c[j - 1] + 1) {
                    for (int k = max(0LL, vec2[(upper_bound(vec2.begin(), vec2.end(), i) - vec2.begin()) - 1] - c[j - 1] - 1); k <= i - c[j - 1] - 1; k++) {
                        dp1[j][i] += dp1[j - 1][k];
                        dp1[j][i] %= MOD;
                    }
                }
                if (j == m && vec2[vec2.size() - 1] > i) {
                    dp1[j][i] = 0;
                }
            }
            // dp1[j][i] += dp1[j][i - 1];
            // dp1[j][i] %= MOD;
        }
    }
    for (int j = 1; j <= m; j++) {
        for (int i = 1; i <= n; i++) {
            dp1[j][i] += dp1[j][i - 1];
            dp1[j][i] %= MOD;
            // cout << j << ' ' << i << ' ' << dp1[j][i] << '\n';
        }
        // cout << '\n';
    }
    // cout << '\n';
    return dp1;
}

string solve_puzzle(string s, vector<int> c) {
    n = s.size();
    m = c.size();
    string ans;
    auto dp1 = do_dp(s, c);
    reverse(c.begin(), c.end());
    reverse(s.begin(), s.end());
    auto dp2 = do_dp(s, c);
    reverse(c.begin(), c.end());
    reverse(s.begin(), s.end());
    vector<ll> vec(1, 0);
    for (int i = 0; i < n; i++) {
        if (s[i] == '_') {
            vec.push_back(i + 1);
        }
    }
    vector<ll> cnt(n + 1);
    for (int j = 0; j < m; j++) {
        for (int i = c[j] + (j != 0 ? 1 : 0); (n + 1 - i) - 1 - (j != m - 1 ? 1 : 0) >= 0; i++) {
            // cout << j << ' ' << i << '\n';
            if (i - vec[(upper_bound(vec.begin(), vec.end(), i) - vec.begin()) - 1] < c[j]) {
                continue;
            }
            if (i > c[j] && s[i - c[j] - 1] == 'X') {
                continue;
            }
            if (i < n && s[i] == 'X') {
                continue;
            }
            // cout << j << ' ' << i << endl;
            ll num = dp1[j][i - c[j] - (j != 0 ? 1 : 0)];
            // cout << num << endl;
            // cout << m - 1 - j << ' ' << (n + 1 - i) - 1 - (j != m - 1 ? 1 : 0) << endl;
            num *= dp2[m - 1 - j][(n + 1 - i) - 1 - (j != m - 1 ? 1 : 0)];
            num %= MOD;
            // cout << num << endl;
            cnt[i - c[j]] += num;
            cnt[i - c[j]] %= MOD;
            cnt[i] += MOD - num;
            cnt[i] %= MOD;
            // cout << '\n';
        }
    }
    // cout << "DEBUG" << endl;
    for (int i = 0; i < n; i++) {
        cnt[i] %= MOD;
        // cout << i << ' ' << cnt[i] << endl;
        cnt[i + 1] += cnt[i];
        // cout << i << endl;
        if (cnt[i] == 0) {
            ans += '_';
        }
        else if (cnt[i] == dp1[m][n]) {
            ans += 'X';
        }
        else {
            ans += '?';
        }
    }
    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 0 ms 348 KB n = 20, m = 1
7 Correct 0 ms 344 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 0 ms 348 KB n = 20, m = 1
7 Correct 0 ms 344 KB n = 20, m = 1
8 Correct 0 ms 344 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 0 ms 348 KB n = 20, m = 1
7 Correct 0 ms 344 KB n = 20, m = 1
8 Correct 0 ms 344 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 0 ms 348 KB n = 100, m = 5
21 Correct 0 ms 344 KB n = 90, m = 3
22 Correct 0 ms 348 KB n = 86, m = 2
23 Correct 0 ms 348 KB n = 81, m = 4
24 Correct 1 ms 348 KB n = 89, m = 10
25 Correct 1 ms 348 KB n = 81, m = 23
26 Correct 0 ms 348 KB n = 86, m = 8
27 Correct 0 ms 348 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 2 ms 348 KB n = 100, m = 50
31 Correct 2 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 0 ms 348 KB n = 20, m = 1
7 Correct 0 ms 344 KB n = 20, m = 1
8 Correct 0 ms 344 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 0 ms 348 KB n = 100, m = 5
21 Correct 0 ms 344 KB n = 90, m = 3
22 Correct 0 ms 348 KB n = 86, m = 2
23 Correct 0 ms 348 KB n = 81, m = 4
24 Correct 1 ms 348 KB n = 89, m = 10
25 Correct 1 ms 348 KB n = 81, m = 23
26 Correct 0 ms 348 KB n = 86, m = 8
27 Correct 0 ms 348 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 2 ms 348 KB n = 100, m = 50
31 Correct 2 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 448 KB n = 86, m = 2
36 Correct 1 ms 604 KB n = 81, m = 6
37 Correct 0 ms 344 KB n = 98, m = 7
38 Correct 1 ms 348 KB n = 92, m = 7
39 Correct 1 ms 348 KB n = 88, m = 21
40 Correct 1 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 0 ms 348 KB n = 20, m = 1
7 Correct 0 ms 344 KB n = 20, m = 1
8 Correct 0 ms 344 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 0 ms 348 KB n = 100, m = 5
21 Correct 0 ms 344 KB n = 90, m = 3
22 Correct 0 ms 348 KB n = 86, m = 2
23 Correct 0 ms 348 KB n = 81, m = 4
24 Correct 1 ms 348 KB n = 89, m = 10
25 Correct 1 ms 348 KB n = 81, m = 23
26 Correct 0 ms 348 KB n = 86, m = 8
27 Correct 0 ms 348 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 2 ms 348 KB n = 100, m = 50
31 Correct 2 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 448 KB n = 86, m = 2
36 Correct 1 ms 604 KB n = 81, m = 6
37 Correct 0 ms 344 KB n = 98, m = 7
38 Correct 1 ms 348 KB n = 92, m = 7
39 Correct 1 ms 348 KB n = 88, m = 21
40 Correct 1 ms 348 KB n = 90, m = 21
41 Correct 1 ms 348 KB n = 98, m = 22
42 Incorrect 1 ms 344 KB char #5 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 0 ms 348 KB n = 20, m = 1
7 Correct 0 ms 344 KB n = 20, m = 1
8 Correct 0 ms 344 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 0 ms 348 KB n = 100, m = 5
21 Correct 0 ms 344 KB n = 90, m = 3
22 Correct 0 ms 348 KB n = 86, m = 2
23 Correct 0 ms 348 KB n = 81, m = 4
24 Correct 1 ms 348 KB n = 89, m = 10
25 Correct 1 ms 348 KB n = 81, m = 23
26 Correct 0 ms 348 KB n = 86, m = 8
27 Correct 0 ms 348 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 2 ms 348 KB n = 100, m = 50
31 Correct 2 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 448 KB n = 86, m = 2
36 Correct 1 ms 604 KB n = 81, m = 6
37 Correct 0 ms 344 KB n = 98, m = 7
38 Correct 1 ms 348 KB n = 92, m = 7
39 Correct 1 ms 348 KB n = 88, m = 21
40 Correct 1 ms 348 KB n = 90, m = 21
41 Correct 1 ms 348 KB n = 98, m = 22
42 Incorrect 1 ms 344 KB char #5 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 0 ms 348 KB n = 20, m = 1
7 Correct 0 ms 344 KB n = 20, m = 1
8 Correct 0 ms 344 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 0 ms 348 KB n = 100, m = 5
21 Correct 0 ms 344 KB n = 90, m = 3
22 Correct 0 ms 348 KB n = 86, m = 2
23 Correct 0 ms 348 KB n = 81, m = 4
24 Correct 1 ms 348 KB n = 89, m = 10
25 Correct 1 ms 348 KB n = 81, m = 23
26 Correct 0 ms 348 KB n = 86, m = 8
27 Correct 0 ms 348 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 2 ms 348 KB n = 100, m = 50
31 Correct 2 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 448 KB n = 86, m = 2
36 Correct 1 ms 604 KB n = 81, m = 6
37 Correct 0 ms 344 KB n = 98, m = 7
38 Correct 1 ms 348 KB n = 92, m = 7
39 Correct 1 ms 348 KB n = 88, m = 21
40 Correct 1 ms 348 KB n = 90, m = 21
41 Correct 1 ms 348 KB n = 98, m = 22
42 Incorrect 1 ms 344 KB char #5 differ - expected: 'X', found: '?'
43 Halted 0 ms 0 KB -