oj.uz

Submission #837206

# Submission time Handle Problem Language Result Execution time Memory
837206 2023-08-25T08:05:31 Z tengiz05 Digital Circuit (IOI22_circuit) C++17
16 / 100
 1384 ms 2097152 KB 
#include "circuit.h"

#include <vector>
#include <array>
#include <iostream>
#include <algorithm>
using namespace std;
constexpr int P = 1E9 + 2022;
int norm(int x) {
    if (x < 0) x += P;
    if (x >= P) x -= P;
    return  x;
}
struct Z {
    int x;
    Z(int x = 0) : x(norm(x)) {}
    int val() { return x; }
    friend Z operator+(const Z &a, const Z &b) {
        return Z(a.x + b.x);
    }
    friend Z operator-(const Z &a, const Z &b) {
        return Z(a.x - b.x);
    }
    friend Z operator*(const Z &a, const Z &b) {
        return Z(int(a.x * 1LL * b.x % P));
    }
    void operator += (const Z &o) {
        *this = *this + o;
    }
};

int n, m;
vector<int> a;
vector<vector<int>> e;
vector<array<Z, 2>> res, rev;
vector<int> lazy;

void init(int N, int M, std::vector<int> P, std::vector<int> A) {
    n = N;
    m = M;
    e.resize(n);
    a = A;
    for (int i = 1; i < n + m; i++) {
        e[P[i]].push_back(i);
    }
    lazy.resize(n + m);
    res.resize(n + m);
    rev.resize(n + m);
    for (int i = 0; i < m; i++) {
        res[n + i][a[i]] = 1;
        rev[n + i][a[i] ^ 1] = 1;
    }
    for (int i = n - 1; i >= 0; i--) {
        vector<Z> dp(e[i].size() + 1);
        dp[0] = 1;
        for (int j : e[i]) {
            vector<Z> ndp(e[i].size() + 1);
            for (int k = e[i].size(); k >= 0; k--) {
                if (k < int(e[i].size())) {
                    ndp[k + 1] += dp[k] * res[j][1];
                }
                ndp[k] += dp[k] * res[j][0];
            }
            dp = ndp;
        }
        int c = e[i].size();
        res[i][0] = res[i][1] = 0;
        res[i][0] += dp[0] * c;
        for (int j = 1; j < int(dp.size()); j++) {
            res[i][1] += dp[j] * j;
            res[i][0] += dp[j] * (c - j);
        }
    }
    for (int i = n - 1; i >= 0; i--) {
        vector<Z> dp(e[i].size() + 1);
        dp[0] = 1;
        for (int j : e[i]) {
            vector<Z> ndp(e[i].size() + 1);
            for (int k = e[i].size(); k >= 0; k--) {
                if (k < int(e[i].size())) {
                    ndp[k + 1] += dp[k] * rev[j][1];
                }
                ndp[k] += dp[k] * rev[j][0];
            }
            dp = ndp;
        }
        int c = e[i].size();
        rev[i][0] = rev[i][1] = 0;
        rev[i][0] += dp[0] * c;
        for (int j = 1; j < int(dp.size()); j++) {
            rev[i][1] += dp[j] * j;
            rev[i][0] += dp[j] * (c - j);
        }
    }
}
int count_ways(int L, int R) {
    R++;
    L -= n;
    R -= n;
    
    auto push = [&](int p) {
        if (lazy[p]) {
            swap(res[2 * p + 1], rev[2 * p + 1]);
            swap(res[2 * p + 2], rev[2 * p + 2]);
            lazy[2 * p + 1] ^= 1;
            lazy[2 * p + 2] ^= 1;
            lazy[p] = 0;
        }
    };
    function<void(int, int, int, int, int)> rangeApply = [&](int p, int l, int r, int x, int y) {
        if (r <= x || y <= l) return;
        if (x <= l && r <= y) {
            swap(res[p], rev[p]);
            lazy[p] ^= 1;
            return;
        }
        push(p);
        int m = (l + r) / 2;
        rangeApply(2 * p + 1, l, m, x, y);
        rangeApply(2 * p + 2, m, r, x, y);
        {
            int i = p;
            vector<Z> dp(e[i].size() + 1);
            dp[0] = 1;
            for (int j : e[i]) {
                vector<Z> ndp(e[i].size() + 1);
                for (int k = e[i].size(); k >= 0; k--) {
                    if (k < int(e[i].size())) {
                        ndp[k + 1] += dp[k] * res[j][1];
                    }
                    ndp[k] += dp[k] * res[j][0];
                }
                dp = ndp;
            }
            int c = e[i].size();
            res[i][0] = res[i][1] = 0;
            res[i][0] += dp[0] * c;
            for (int j = 1; j < int(dp.size()); j++) {
                res[i][1] += dp[j] * j;
                res[i][0] += dp[j] * (c - j);
            }
        } {
            int i = p;
            vector<Z> dp(e[i].size() + 1);
            dp[0] = 1;
            for (int j : e[i]) {
                vector<Z> ndp(e[i].size() + 1);
                for (int k = e[i].size(); k >= 0; k--) {
                    if (k < int(e[i].size())) {
                        ndp[k + 1] += dp[k] * rev[j][1];
                    }
                    ndp[k] += dp[k] * rev[j][0];
                }
                dp = ndp;
            }
            int c = e[i].size();
            rev[i][0] = rev[i][1] = 0;
            rev[i][0] += dp[0] * c;
            for (int j = 1; j < int(dp.size()); j++) {
                rev[i][1] += dp[j] * j;
                rev[i][0] += dp[j] * (c - j);
            }
        }
    };
    
    rangeApply(0, 0, m, L, R);
    
    return res[0][1].val();
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Runtime error 762 ms 2097152 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

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

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Runtime error 762 ms 2097152 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 716 ms 4284 KB Output is correct
2 Correct 1151 ms 8248 KB Output is correct
3 Correct 1014 ms 8272 KB Output is correct
4 Correct 1074 ms 8272 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 716 ms 4284 KB Output is correct
2 Correct 1151 ms 8248 KB Output is correct
3 Correct 1014 ms 8272 KB Output is correct
4 Correct 1074 ms 8272 KB Output is correct
5 Correct 1071 ms 4432 KB Output is correct
6 Correct 1116 ms 8272 KB Output is correct
7 Correct 1384 ms 8264 KB Output is correct
8 Correct 1236 ms 8172 KB Output is correct
9 Correct 583 ms 464 KB Output is correct
10 Correct 1110 ms 720 KB Output is correct
11 Correct 975 ms 720 KB Output is correct
12 Correct 1134 ms 720 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 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Incorrect 1 ms 460 KB 1st lines differ - on the 1st token, expected: '706880838', found: '644103476'
7 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Runtime error 762 ms 2097152 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Runtime error 762 ms 2097152 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -