oj.uz

Submission #786444

# Submission time Handle Problem Language Result Execution time Memory
786444 2023-07-18T07:53:10 Z vjudge1 Digital Circuit (IOI22_circuit) C++17
23 / 100
 3000 ms 10424 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), on(N + M), off(N + M);
    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 x = ch[i][0];
            int y = ch[i][1];
            tot[i] = mul(2, mul(tot[x], tot[y]));
            on[i] = add(mul(tot[x], on[y]), mul(tot[y], on[x]));
            off[i] = sub(tot[i], on[i]);
        }
    }
    return on[0];
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Incorrect 0 ms 208 KB 1st lines differ - on the 1st token, expected: '1', found: '0'
3 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 396 KB Output is correct
12 Correct 1 ms 336 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Incorrect 0 ms 208 KB 1st lines differ - on the 1st token, expected: '1', found: '0'
3 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 515 ms 3968 KB Output is correct
2 Correct 683 ms 7704 KB Output is correct
3 Correct 751 ms 7708 KB Output is correct
4 Correct 694 ms 7728 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 515 ms 3968 KB Output is correct
2 Correct 683 ms 7704 KB Output is correct
3 Correct 751 ms 7708 KB Output is correct
4 Correct 694 ms 7728 KB Output is correct
5 Correct 554 ms 3944 KB Output is correct
6 Correct 770 ms 7724 KB Output is correct
7 Correct 848 ms 7752 KB Output is correct
8 Correct 782 ms 7724 KB Output is correct
9 Correct 389 ms 504 KB Output is correct
10 Correct 718 ms 736 KB Output is correct
11 Correct 596 ms 736 KB Output is correct
12 Correct 590 ms 744 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 1 ms 208 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 396 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 515 ms 3968 KB Output is correct
14 Correct 683 ms 7704 KB Output is correct
15 Correct 751 ms 7708 KB Output is correct
16 Correct 694 ms 7728 KB Output is correct
17 Correct 554 ms 3944 KB Output is correct
18 Correct 770 ms 7724 KB Output is correct
19 Correct 848 ms 7752 KB Output is correct
20 Correct 782 ms 7724 KB Output is correct
21 Correct 389 ms 504 KB Output is correct
22 Correct 718 ms 736 KB Output is correct
23 Correct 596 ms 736 KB Output is correct
24 Correct 590 ms 744 KB Output is correct
25 Execution timed out 3057 ms 10424 KB Time limit exceeded
26 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 Incorrect 0 ms 208 KB 1st lines differ - on the 1st token, expected: '1', found: '0'
3 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 Incorrect 0 ms 208 KB 1st lines differ - on the 1st token, expected: '1', found: '0'
3 Halted 0 ms 0 KB -