QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#468755#8335. Fast Hash Transformreal_sigma_team#WA 7ms54400kbC++173.4kb2024-07-09 00:17:292024-07-09 00:17:29

Judging History

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

  • [2024-07-09 00:17:29]
  • 评测
  • 测评结果:WA
  • 用时:7ms
  • 内存:54400kb
  • [2024-07-09 00:17:29]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;

struct SqrtTreeItem {
    array<uint64_t, 64> arr;
    uint64_t xr = 0;

    SqrtTreeItem() {
        arr.fill(0);
        xr = 0;
    }
};

SqrtTreeItem op(const SqrtTreeItem &a, const SqrtTreeItem &b) {
    SqrtTreeItem res;
    res.xr = b.xr;
    for (int i = 0; i < 64; ++i) {
        for (int j = 0; j < 64; ++j) {
            if (b.arr[i] >> j & 1) {
                res.xr ^= (a.xr >> j & 1) << i;
                res.arr[i] ^= a.arr[j];
            }
        }
    }
    return res;
}

uint64_t go(const SqrtTreeItem& a, uint64_t x) {
    uint64_t res = a.xr;
    for (int i = 0; i < 64; ++i) {
        int c = __builtin_popcount(a.arr[i] & x) & 1;
        if (c) res ^= 1ull << i;
    }
    return res;
}

const int N = 20000;
SqrtTreeItem tr[4 * N], v[N];

void build(int node, int l, int r) {
    if (l == r) {
        tr[node] = v[l];
    } else {
        int m = (l + r) / 2;
        build(node << 1, l, m);
        build(node << 1 | 1, m + 1, r);
        tr[node] = op(tr[node << 1], tr[node << 1 | 1]);
    }
}

void update(int k, int node, int l, int r) {
    if (l == r) {
        tr[node] = v[l];
    } else {
        int m = (l + r) / 2;
        if (k <= m) update(k, node << 1, l, m);
        else update(k, node << 1 | 1, m + 1, r);
        tr[node] = op(tr[node << 1], tr[node << 1 | 1]);
    }
}

uint64_t ret;

void go(int ql, int qr, int node, int l, int r) {
    if (r < ql || qr < l) return;
    if (ql <= l && r <= qr) {
        ret = go(tr[node], ret);
        return;
    }
    int m = (l + r) / 2;
    go(ql, qr, node << 1, l, m);
    go(ql, qr, node << 1 | 1, m + 1, r);
}


int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int n, q, c;
    cin >> n >> q >> c;
    for (int i = 0; i < n; ++i) {
        int m;
        cin >> m;
        vector<tuple<int, int, uint64_t>> res(m);
        for (auto &[s, o, A]: res) cin >> s >> o >> A;
        cin >> v[i].xr;
        for (int j = 0; j < 64; ++j) {
            for (auto [s, o, A]: res) {
                int k = j + s;
                if (k >= 64) k -= 64;
                if (o == 0 && (A >> k & 1)) v[i].xr ^= 1ull << k;
                else if (o == 1 && (~A >> k & 1)) {}
                else {
                    v[i].arr[k] ^= 1ull << j;
                }
            }
        }
    }
    build(1, 0, n - 1);
    while (q--) {
        int op;
        cin >> op;
        if (op == 0) {
            int l, r;
            cin >> l >> r >> ret;
            --l, --r;
            go(l, r, 1, 0, n - 1);
            cout << ret << '\n';
        } else {
            int i;
            cin >> i;
            --i;
            v[i] = SqrtTreeItem();
            int m;
            cin >> m;
            vector<tuple<int, int, uint64_t>> res(m);
            for (auto &[s, o, A]: res) cin >> s >> o >> A;
            cin >> v[i].xr;
            for (int j = 0; j < 64; ++j) {
                for (auto [s, o, A]: res) {
                    int k = j + s;
                    if (k >= 64) k -= 64;
                    if (o == 0 && (A >> k & 1)) v[i].xr ^= 1ull << k;
                    else if (o == 1 && (~A >> k & 1)) {}
                    else {
                        v[i].arr[k] ^= 1ull << j;
                    }
                }
            }
            update(i, 1, 0, n - 1);
        }
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 4ms
memory: 54300kb

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: 7ms
memory: 54400kb

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:

12577215260167111646
17994401072732780685
8676206739352849697
5292801977632587806
112919739392362481
17580801933839203485

result:

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