QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#468755 | #8335. Fast Hash Transform | real_sigma_team# | WA | 7ms | 54400kb | C++17 | 3.4kb | 2024-07-09 00:17:29 | 2024-07-09 00:17:29 |
Judging History
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'