oj.uz

Submission #968024

# Submission time Handle Problem Language Result Execution time Memory
968024 2024-04-23T06:59:40 Z weakweakweak Binaria (CCO23_day1problem1) C++17
10 / 25
 60 ms 16720 KB 
#include <bits/stdc++.h>
using namespace std;

int a[501000], ch[501000], fa[501000], dp[501000] = {0};

int find (int x) {
    return fa[x] == x ? x : fa[x] = find (fa[x]);
}

void merge (int i, int j) {
    i = find(i), j = find(j);
    if (i == j) return;
    fa[i] = j;
    if (ch[i] == 3 or ch[j] == 3) ch[j] = min(ch[i], ch[j]);
    else if (ch[i] != ch[j]) {
        cout << "0\n";
        exit(0);
    }
}

void f(int i, int val) {
    i = find(i);
    if (ch[i] == 3) ch[i] = val;
    else if (ch[i] != val) {
        cout << "0\n";
        exit(0);
    }
}

int main () {
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) fa[i] = i, ch[i] = 3;
    for (int i = 1; i + k - 1 <= n; i++) cin >> a[i];
    for (int i = 2; i + k - 1 <= n; i++) {
        int dif = a[i] - a[i - 1];
        if (dif == 0) merge(i - 1, i + k - 1);
        else if (dif == 1) f(i + k - 1, 1), f(i - 1, 0);
        else f(i + k - 1, 0), f(i - 1, 1);
    }

    int left = a[1];
    map <int,int> mp;
    // for (int i = 1; i <= n; i++) cout << find(i) << ' '; cout << '\n';
    // for (int i = 1; i <= n; i++) cout << ch[find(i)] << ' '; cout << '\n';
    for (int i = 1; i <= k; i++) {
        if (ch[find(i)] == 3) mp[find(i)]++;
        else if (ch[find(i)] == 1) {
            left--;
        }
    }

    dp[0] = 1;
    for (auto [x, y] : mp) {
        // cout << y << ' ' << left << '\n';
        for (int i = left; i >= y; i--) dp[i] += dp[i - y];
    }
    cout << dp[left] << '\n';
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6488 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6488 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6488 KB Output is correct
16 Correct 1 ms 6488 KB Output is correct
17 Correct 1 ms 6492 KB Output is correct
18 Correct 1 ms 6492 KB Output is correct
19 Correct 1 ms 6488 KB Output is correct
20 Correct 1 ms 6492 KB Output is correct
21 Correct 1 ms 6492 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6488 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6488 KB Output is correct
16 Correct 1 ms 6488 KB Output is correct
17 Correct 1 ms 6492 KB Output is correct
18 Correct 1 ms 6492 KB Output is correct
19 Correct 1 ms 6488 KB Output is correct
20 Correct 1 ms 6492 KB Output is correct
21 Correct 1 ms 6492 KB Output is correct
22 Correct 1 ms 6488 KB Output is correct
23 Correct 1 ms 6492 KB Output is correct
24 Correct 1 ms 6588 KB Output is correct
25 Correct 1 ms 6492 KB Output is correct
26 Correct 1 ms 6492 KB Output is correct
27 Correct 1 ms 6492 KB Output is correct
28 Correct 1 ms 6492 KB Output is correct
29 Correct 1 ms 6604 KB Output is correct
30 Correct 1 ms 6492 KB Output is correct
31 Correct 1 ms 6500 KB Output is correct
32 Correct 1 ms 6492 KB Output is correct
33 Correct 1 ms 6488 KB Output is correct
34 Correct 1 ms 6492 KB Output is correct

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6488 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6488 KB Output is correct
16 Correct 1 ms 6488 KB Output is correct
17 Correct 1 ms 6492 KB Output is correct
18 Correct 1 ms 6492 KB Output is correct
19 Correct 1 ms 6488 KB Output is correct
20 Correct 1 ms 6492 KB Output is correct
21 Correct 1 ms 6492 KB Output is correct
22 Correct 1 ms 6488 KB Output is correct
23 Correct 1 ms 6492 KB Output is correct
24 Correct 1 ms 6588 KB Output is correct
25 Correct 1 ms 6492 KB Output is correct
26 Correct 1 ms 6492 KB Output is correct
27 Correct 1 ms 6492 KB Output is correct
28 Correct 1 ms 6492 KB Output is correct
29 Correct 1 ms 6604 KB Output is correct
30 Correct 1 ms 6492 KB Output is correct
31 Correct 1 ms 6500 KB Output is correct
32 Correct 1 ms 6492 KB Output is correct
33 Correct 1 ms 6488 KB Output is correct
34 Correct 1 ms 6492 KB Output is correct
35 Runtime error 60 ms 16720 KB Execution killed with signal 11
36 Halted 0 ms 0 KB -

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6488 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6488 KB Output is correct
16 Correct 1 ms 6488 KB Output is correct
17 Correct 1 ms 6492 KB Output is correct
18 Correct 1 ms 6492 KB Output is correct
19 Correct 1 ms 6488 KB Output is correct
20 Correct 1 ms 6492 KB Output is correct
21 Correct 1 ms 6492 KB Output is correct
22 Correct 1 ms 6488 KB Output is correct
23 Correct 1 ms 6492 KB Output is correct
24 Correct 1 ms 6588 KB Output is correct
25 Correct 1 ms 6492 KB Output is correct
26 Correct 1 ms 6492 KB Output is correct
27 Correct 1 ms 6492 KB Output is correct
28 Correct 1 ms 6492 KB Output is correct
29 Correct 1 ms 6604 KB Output is correct
30 Correct 1 ms 6492 KB Output is correct
31 Correct 1 ms 6500 KB Output is correct
32 Correct 1 ms 6492 KB Output is correct
33 Correct 1 ms 6488 KB Output is correct
34 Correct 1 ms 6492 KB Output is correct
35 Runtime error 60 ms 16720 KB Execution killed with signal 11
36 Halted 0 ms 0 KB -

Subtask #6
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6488 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6488 KB Output is correct
16 Correct 1 ms 6488 KB Output is correct
17 Correct 1 ms 6492 KB Output is correct
18 Correct 1 ms 6492 KB Output is correct
19 Correct 1 ms 6488 KB Output is correct
20 Correct 1 ms 6492 KB Output is correct
21 Correct 1 ms 6492 KB Output is correct
22 Correct 1 ms 6488 KB Output is correct
23 Correct 1 ms 6492 KB Output is correct
24 Correct 1 ms 6588 KB Output is correct
25 Correct 1 ms 6492 KB Output is correct
26 Correct 1 ms 6492 KB Output is correct
27 Correct 1 ms 6492 KB Output is correct
28 Correct 1 ms 6492 KB Output is correct
29 Correct 1 ms 6604 KB Output is correct
30 Correct 1 ms 6492 KB Output is correct
31 Correct 1 ms 6500 KB Output is correct
32 Correct 1 ms 6492 KB Output is correct
33 Correct 1 ms 6488 KB Output is correct
34 Correct 1 ms 6492 KB Output is correct
35 Runtime error 60 ms 16720 KB Execution killed with signal 11
36 Halted 0 ms 0 KB -