답안 #786444

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
786444	2023-07-18T07:53:10 Z	vjudge1	디지털 회로 (IOI22_circuit)	C++17	23 / 100	3000 ms	10424 KB

circuit

#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

#	결과	메모리	Grader output
1	Correct	208 KB	Output is correct
2	Incorrect	208 KB	1st lines differ - on the 1st token, expected: '1', found: '0'
3	Halted	0 KB	-

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	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

#	결과	메모리	Grader output
1	Correct	208 KB	Output is correct
2	Incorrect	208 KB	1st lines differ - on the 1st token, expected: '1', found: '0'
3	Halted	0 KB	-

Subtask #4
4.0 / 4.0

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	메모리	Grader output
1	Correct	208 KB	Output is correct
2	Incorrect	208 KB	1st lines differ - on the 1st token, expected: '1', found: '0'
3	Halted	0 KB	-

Subtask #8
0 / 11.0

#	결과	메모리	Grader output
1	Correct	208 KB	Output is correct
2	Incorrect	208 KB	1st lines differ - on the 1st token, expected: '1', found: '0'
3	Halted	0 KB	-

답안 #786444

Compilation message