QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#353752#8335. Fast Hash Transformucup-team004#WA 1ms3840kbC++203.0kb2024-03-14 15:52:112024-03-14 15:52:13

Judging History

你现在查看的是最新测评结果

  • [2024-03-14 15:52:13]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3840kb
  • [2024-03-14 15:52:11]
  • 提交

answer

#include <bits/stdc++.h>

using i64 = long long;
using u64 = long long;

using Matrix = std::array<u64, 65>;

Matrix operator*(const Matrix &a, const Matrix &b) {
    Matrix c{};
    for (int i = 0; i <= 64; i++) {
        for (int j = 0; j <= 64; j++) {
            if (j == 64 || (a[i] >> j & 1)) {
                c[i] ^= b[j];
            }
        }
    }
    return c;
}

u64 operator*(u64 a, const Matrix &b) {
    u64 c = 0;
    for (int i = 0; i <= 64; i++) {
        if (i == 64 || (a >> i & 1)) {
            c ^= b[i];
        }
    }
    return c;
}

Matrix readMatrix() {
    int m;
    std::cin >> m;

    Matrix f{};
    for (int i = 0; i < m; i++) {
        int s, o;
        u64 A;
        std::cin >> s >> o >> A;

        if (o == 0) {
            for (int j = 0; j < 64; j++) {
                if (A >> ((j + s) % 64) & 1) {
                    f[64] ^= 1ULL << ((j + s) % 64);
                } else {
                    f[j] ^= 1ULL << ((j + s) % 64);
                }
            }
        } else {
            for (int j = 0; j < 64; j++) {
                if (A >> ((j + s) % 64) & 1) {
                    f[j] ^= 1ULL << ((j + s) % 64);
                }
            }
        }
    }

    u64 B;
    std::cin >> B;
    f[64] ^= B;

    return f;
}

constexpr int B = 100;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int N, Q, C;
    std::cin >> N >> Q >> C;

    std::vector<Matrix> f(N);
    for (int i = 0; i < N; i++) {
        f[i] = readMatrix();
    }

    int numBlock = (N + B - 1) / B;
    std::vector<Matrix> prod(numBlock);

    auto build = [&](int i) {
        int L = i * B;
        int R = std::min(N, L + B);
        for (int j = 0; j < 64; j++) {
            prod[i][j] = 1ULL << j;
        }
        for (int j = L; j < R; j++) {
            prod[i] = prod[i] * f[j];
        }
    };
    for (int i = 0; i < numBlock; i++) {
        build(i);
    }

    for (int i = 0; i < Q; i++) {
        int op;
        std::cin >> op;

        if (op == 0) {
            int l, r;
            u64 x;
            std::cin >> l >> r >> x;
            l--;

            if (l / B == (r - 1) / B) {
                for (int j = l; j < r; j++) {
                    x = x * f[j];
                }
            } else {
                int lb = l / B, rb = (r - 1) / B;
                for (int j = l; j < (lb + 1) * B; j++) {
                    x = x * f[j];
                }
                for (int j = lb + 1; j < rb; j++) {
                    x = x * prod[j];
                }
                for (int j = rb * B; j < r; j++) {
                    x = x * f[j];
                }
            }
            std::cout << x << "\n";
        } else {
            int l;
            std::cin >> l;
            l--;
            f[l] = readMatrix();
            build(l / B);
        }
    }
    
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3840kb

input:

3 5 1
1 4 0 0 51966
1 60 0 0 0
1 0 0 16 15
0 1 1 771
0 2 2 32368
0 3 3 0
1 2 2 0 0 15 61 1 4095 46681
0 1 3 2023

output:

64206
2023
31
1112

result:

ok 4 tokens

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 3504kb

input:

9 9 3
32 9 0 17785061119123981789 33 0 10890571864137198682 42 0 9437574736788763477 34 0 5239651887868507470 55 0 14741743279679654187 27 1 1444116632918569317 38 1 5740886562180922636 1 1 8113356142324084796 3 0 10955266306442425904 60 0 16421026339459788005 53 0 1595107134632608917 48 1 923204972...

output:

4689
4689
4689
4689
4689
4689
4689
4689
4689

result:

wrong answer 1st words differ - expected: '9487331362121050549', found: '4689'