oj.uz

Submission #786451

# Submission time Handle Problem Language Result Execution time Memory
786451 2023-07-18T07:58:49 Z vjudge1 Digital Circuit (IOI22_circuit) C++17
18 / 100
 850 ms 7752 KB 
#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
constexpr int mod = 1000002022;
int N, M;
vector<int> P, A, st, lazy, len;
vector<vector<int>> ch;
int add(int a, int b) {
    int c = a + b;
    if (c >= mod) {
        c -= mod;
    }
    return c;
}
int mul(int a, int b) {
    return 1LL * a * b % mod;
}
int sub(int a, int b) {
    int c = a - b;
    if (c < 0) {
        c += mod;
    }
    return c;
}
int cont;
bool bintree;
void apply(int p, int z) {
    if (z == 0) {
        return;
    }
    st[p] = len[p] - st[p];
    lazy[p] ^= 1;
}
void pull(int p) {
    st[p] = st[p * 2] + st[p * 2 + 1];
}
void push(int p) {
    apply(p * 2, lazy[p]);
    apply(p * 2 + 1, lazy[p]);
    lazy[p] = 0;
}
void update(int p, int l, int r, int L, int R) {
    if (R <= l || r <= L) {
        return;
    }
    if (L <= l && r <= R) {
        apply(p, 1);
        return;
    }
    int m = (l + r) / 2;
    push(p);
    update(p * 2, l, m, L, R);
    update(p * 2 + 1, m, r, L, R);
    pull(p);
}
void init(int n, int m, vector<int> p, vector<int> a) {
    N = n, M = m;
    P = p, A = a;
    ch.resize(N);
    for (int i = 1; i < N + M; i++) {
        ch[P[i]].push_back(i);
    }
    bintree = 0;
    if (N + 1 == M && __builtin_popcount(M) == 1) {
        bintree = 1;
        for (int i = 1; i < N + M; i++) {
            if (P[i] != (i - 1) / 2) {
                bintree = 0;
            }
        }
        if (bintree) {
            int lg = __lg(M);
            cont = 1;
            int s = 1;
            for (int i = 0; i < lg; i++) {
                cont = mul(cont, s);
                s = mul(2, mul(s, s));
            }
            st.resize(2 * M);
            len.resize(2 * M);
            lazy.resize(2 * M);
            for (int i = 0; i < M; i++) {
                st[i + M] = A[i];
                len[i + M] = 1;
            }
            for (int i = M - 1; i; i--) {
                st[i] = st[i * 2] + st[i * 2 + 1];
                len[i] = len[i * 2] + len[i * 2 + 1];
            }
        }
    }
}
int count_ways(int L, int R) {
    if (bintree) {
        update(1, 0, M, L - N, R - N + 1);
        return mul(st[1], cont);
    }
    for (int i = L; i <= R; i++) {
        A[i - N] ^= 1;
    }
    vector<int> tot(N + M, 1), on(N + M), off(N + M);
    vector dp(N, vector{1});
    for (int i = N + M - 1; i >= 0; i--) {
        if (i >= N) {
            tot[i] = 1;
            if (A[i - N] == 0) {
                off[i] = 1;
            } else {
                on[i] = 1;
            }
        } else {
            int f = ch[i].size();
            for (int j = 1; j <= f; j++) {
                on[i] = add(on[i], mul(dp[i][j], j));
            }
            tot[i] = mul(tot[i], f);
            off[i] = sub(tot[i], on[i]);
        }
        if (i) {
            tot[P[i]] = mul(tot[P[i]], tot[i]);
            dp[P[i]].push_back(dp[P[i]].back() * on[i]);
            for (int j = dp[P[i]].size() - 2; j >= 0; j--) {
                dp[P[i]][j] = mul(off[i], dp[P[i]][j]);
                if (j) {
                    dp[P[i]][j] = add(dp[P[i]][j], mul(dp[P[i]][j - 1], on[i]));
                }
            }
        }
    }
    return on[0];
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 12 ms 336 KB Output is correct
4 Correct 13 ms 336 KB Output is correct
5 Correct 14 ms 336 KB Output is correct
6 Correct 16 ms 336 KB Output is correct
7 Correct 13 ms 336 KB Output is correct
8 Correct 13 ms 336 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 360 KB Output is correct
4 Correct 1 ms 356 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Incorrect 1 ms 408 KB 1st lines differ - on the 1st token, expected: '706880838', found: '690851556'
7 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 12 ms 336 KB Output is correct
4 Correct 13 ms 336 KB Output is correct
5 Correct 14 ms 336 KB Output is correct
6 Correct 16 ms 336 KB Output is correct
7 Correct 13 ms 336 KB Output is correct
8 Correct 13 ms 336 KB Output is correct
9 Correct 0 ms 208 KB Output is correct
10 Correct 0 ms 208 KB Output is correct
11 Correct 1 ms 360 KB Output is correct
12 Correct 1 ms 356 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Incorrect 1 ms 408 KB 1st lines differ - on the 1st token, expected: '706880838', found: '690851556'
15 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 472 ms 4004 KB Output is correct
2 Correct 827 ms 7696 KB Output is correct
3 Correct 722 ms 7716 KB Output is correct
4 Correct 722 ms 7712 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 472 ms 4004 KB Output is correct
2 Correct 827 ms 7696 KB Output is correct
3 Correct 722 ms 7716 KB Output is correct
4 Correct 722 ms 7712 KB Output is correct
5 Correct 581 ms 4004 KB Output is correct
6 Correct 839 ms 7752 KB Output is correct
7 Correct 788 ms 7724 KB Output is correct
8 Correct 769 ms 7752 KB Output is correct
9 Correct 331 ms 504 KB Output is correct
10 Correct 850 ms 736 KB Output is correct
11 Correct 674 ms 740 KB Output is correct
12 Correct 668 ms 740 KB Output is correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 360 KB Output is correct
4 Correct 1 ms 356 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Incorrect 1 ms 408 KB 1st lines differ - on the 1st token, expected: '706880838', found: '690851556'
7 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 12 ms 336 KB Output is correct
4 Correct 13 ms 336 KB Output is correct
5 Correct 14 ms 336 KB Output is correct
6 Correct 16 ms 336 KB Output is correct
7 Correct 13 ms 336 KB Output is correct
8 Correct 13 ms 336 KB Output is correct
9 Correct 0 ms 208 KB Output is correct
10 Correct 0 ms 208 KB Output is correct
11 Correct 1 ms 360 KB Output is correct
12 Correct 1 ms 356 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Incorrect 1 ms 408 KB 1st lines differ - on the 1st token, expected: '706880838', found: '690851556'
15 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 12 ms 336 KB Output is correct
4 Correct 13 ms 336 KB Output is correct
5 Correct 14 ms 336 KB Output is correct
6 Correct 16 ms 336 KB Output is correct
7 Correct 13 ms 336 KB Output is correct
8 Correct 13 ms 336 KB Output is correct
9 Correct 0 ms 208 KB Output is correct
10 Correct 0 ms 208 KB Output is correct
11 Correct 1 ms 360 KB Output is correct
12 Correct 1 ms 356 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Incorrect 1 ms 408 KB 1st lines differ - on the 1st token, expected: '706880838', found: '690851556'
15 Halted 0 ms 0 KB -