oj.uz

답안 #798034

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
798034 2023-07-30T09:55:50 Z jakobrs 디지털 회로 (IOI22_circuit) C++17
16 / 100
 744 ms 9308 KB 
#include <iostream>
#include <vector>

using i64 = int64_t;

const i64 MOD = 1'000'002'022;

struct Node {
    i64 a1, a0, ax;

    Node() : a1(0), a0(1), ax(1) {}
    explicit Node(bool value) : a1(value), a0(!value), ax(1) {}
    Node(i64 a1, i64 a0, i64 ax) : a1(a1), a0(a0), ax(ax) {}

    void toggle() { std::swap(a1, a0); }

    Node operator*(const Node &rhs) const {
        return {(a1 * rhs.ax + ax * rhs.a1) % MOD,
                (a0 * rhs.ax + ax * rhs.a0) % MOD, ax * rhs.ax * 2 % MOD};
    }
};

struct SegmentTree {
    std::vector<Node> values;
    std::vector<bool> toggled;
    i64 offset;

    SegmentTree() : values{}, toggled{}, offset{0} {}
    explicit SegmentTree(size_t sz)
        : values(2 * sz), toggled(2 * sz, false), offset(sz) {}

    void update(i64 idx, bool value) {
        idx += offset;

        values[idx] = Node(value);

        while (idx /= 2) pull(idx);
    }

    void toggle_range(i64 l, i64 r) { toggle_range(l, r, 1, 0, offset); }
    void toggle_range(i64 l, i64 r, i64 v, i64 s, i64 e) {
        if (e <= l || r <= s) {
            return;
        } else if (l <= s && e <= r) {
            values[v].toggle();
            toggled[v] = !toggled[v];
        } else {
            i64 m = (s + e) / 2;

            push(v);
            toggle_range(l, r, 2 * v, s, m);
            toggle_range(l, r, 2 * v + 1, m, e);
            pull(v);
        }
    }

    void push(i64 v) {
        if (toggled[v]) {
            toggled[v] = false;

            toggled[2 * v] = !toggled[2 * v];
            toggled[2 * v + 1] = !toggled[2 * v + 1];

            values[2 * v].toggle();
            values[2 * v + 1].toggle();
        }
    }

    void pull(i64 v) { values[v] = values[2 * v] * values[2 * v + 1]; }

    const Node &root() const { return values[1]; }
};

int n, m;
std::vector<int> p, a;

std::vector<std::vector<int>> children;
SegmentTree st;
bool is_45 = true;

void init(int N, int M, std::vector<int> P, std::vector<int> A) {
    n = N;
    m = M;
    p = P;
    a = A;

    children.resize(N);
    for (i64 i = 1; i < N + M; i++) {
        children[P[i]].push_back(i);
    }

    if (M == N + 1 && (M & (M - 1)) == 0) {
        for (i64 i = 0; i < N; i++) {
            if (children[i].size() != 2) {
                is_45 = false;
                break;
            }
        }
    }

    if (is_45) {
        st = SegmentTree(N + 1);

        for (i64 i = 0; i < M; i++) {
            st.update(i, A[i]);
        }
    }
}

auto dfs(int node) -> std::pair<i64, i64> {
    if (node >= n) {
        return {a[node - n] ? 1 : 0, 1};
    }

    i64 cs = children[node].size();
    std::vector<std::pair<i64, i64>> results;
    results.reserve(1 + cs);

    for (i64 c : children[node]) {
        results.push_back(dfs(c));
    }

    std::vector<i64> xs_left{1}, xs_right{1};
    xs_left.reserve(1 + cs);
    xs_right.reserve(1 + cs);

    for (i64 i = 0; i < cs; i++) {
        xs_left.push_back(xs_left.back() * results[i].second % MOD);
        xs_right.push_back(xs_right.back() * results[cs - i - 1].second % MOD);
    }

    i64 sum = 0, of = cs;

    for (i64 i = 0; i < cs; i++) {
        sum += results[i].first * xs_left[i] % MOD * xs_right[cs - i - 1];
        of *= results[i].second;

        sum %= MOD;
        of %= MOD;
    }

    return {sum, of};
}

int count_ways(int l, int r) {
    r += 1;

    l -= n;
    r -= n;

    if (is_45) {
        st.toggle_range(l, r);

        return st.root().a1;
    } else {
        for (i64 i = l; i < r; i++) {
            a[i] = !a[i];
        }

        return dfs(0).first;
    }
}

Subtask #1
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Runtime error 1 ms 464 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #2
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 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '706880838', found: '771166560'
7 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Runtime error 1 ms 464 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 532 ms 4780 KB Output is correct
2 Correct 744 ms 9296 KB Output is correct
3 Correct 679 ms 9308 KB Output is correct
4 Correct 677 ms 9288 KB Output is correct

Subtask #5
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 532 ms 4780 KB Output is correct
2 Correct 744 ms 9296 KB Output is correct
3 Correct 679 ms 9308 KB Output is correct
4 Correct 677 ms 9288 KB Output is correct
5 Correct 601 ms 4772 KB Output is correct
6 Correct 743 ms 9264 KB Output is correct
7 Correct 643 ms 9252 KB Output is correct
8 Correct 720 ms 9272 KB Output is correct
9 Correct 347 ms 464 KB Output is correct
10 Correct 656 ms 848 KB Output is correct
11 Correct 678 ms 848 KB Output is correct
12 Correct 664 ms 864 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 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '706880838', found: '771166560'
7 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Runtime error 1 ms 464 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Runtime error 1 ms 464 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -