oj.uz

답안 #798033

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
798033 2023-07-30T09:54:20 Z jakobrs 디지털 회로 (IOI22_circuit) C++17
16 / 100
 728 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 0 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 0 ms 208 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 0 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 0 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 495 ms 4772 KB Output is correct
2 Correct 621 ms 9228 KB Output is correct
3 Correct 671 ms 9264 KB Output is correct
4 Correct 683 ms 9260 KB Output is correct

Subtask #5
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 495 ms 4772 KB Output is correct
2 Correct 621 ms 9228 KB Output is correct
3 Correct 671 ms 9264 KB Output is correct
4 Correct 683 ms 9260 KB Output is correct
5 Correct 553 ms 4816 KB Output is correct
6 Correct 728 ms 9300 KB Output is correct
7 Correct 665 ms 9252 KB Output is correct
8 Correct 654 ms 9308 KB Output is correct
9 Correct 346 ms 464 KB Output is correct
10 Correct 674 ms 848 KB Output is correct
11 Correct 704 ms 848 KB Output is correct
12 Correct 554 ms 848 KB Output is correct

Subtask #6
0 / 27.0

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