QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#563408 | #8335. Fast Hash Transform | Unique_Hanpi | WA | 2862ms | 5976kb | C++14 | 2.7kb | 2024-09-14 11:23:35 | 2024-09-14 11:23:36 |
Judging History
answer
#include <bits/stdc++.h>
#define lowbit(x) (x & -x)
#define eb emplace_back
#define pb push_back
#define mp make_pair
using namespace std;
typedef unsigned long long ll;
const int N = 20005;
const int B = 200;
const int Mod = 998244353;
int n, q, c;
int loc[N], L[N], R[N];
int s[64], o[64];
ll A[64], BB;
struct f {
bool b[64];
ll c[64];
inline ll calc(ll x) {
ll ret = 0;
for (int i = 0; i < 64; i++)
ret |= (ll(b[i] ^ (__builtin_popcountll(x & c[i]) & 1)) << i);
return ret;
}
} H[N], F[N / B + 2], sf[N / B + 2], pf[N / B + 2];
inline f merge(const f &A, const f &B) {//A after B
f r;
for (int i = 0; i < 64; i++) {
r.c[i] = 0;
r.b[i] = A.b[i];
for (int j = 0; j < 64; j++) if ((A.c[i] >> j) & 1)
r.c[i] ^= B.c[j], r.b[i] ^= B.b[j];
}
return r;
}
inline void rebuild(int id) {
int l = L[id], r = R[id];
F[id] = H[l];
pf[l] = H[l];
for (int i = l + 1; i <= r; i++) {
F[id] = merge(H[i], F[id]);
pf[i] = merge(H[i], pf[i]);
}
sf[r] = H[r];
for (int i = r - 1; i >= l; i--) sf[i] = merge(sf[i], H[i]);
}
inline void read(f &a) {
int m;
scanf("%d", &m);
for (int i = 1; i <= m; i++) scanf("%d", &s[i]), scanf("%d", &o[i]), scanf("%llu", &A[i]);
scanf("%llu", &BB);
for (int i = 0; i < 64; i++) {
a.b[i] = (BB >> i) & 1;
a.c[i] = 0;
for (int j = 1; j <= m; j++) {
int x = (i - s[j] + 64) % 64;
if (o[j] == 0 && (A[j] >> i & 1)) a.b[i] ^= 1;
else if (o[j] == 1 && !(A[j] >> i & 1)) ;
else a.c[i] |= (ll(1) << x);
}
}
}
int main() {
scanf("%d%d%d", &n, &q, &c);
for (int i = 1; i <= n; i++) {
loc[i] = i / B + 1;
if (loc[i] != loc[i - 1]) L[loc[i]] = i;
R[loc[i]] = i;
}
for (int i = 1; i <= n; i++) read(H[i]);
for (int i = 1; i <= loc[n]; i++) rebuild(i);
while (q--) {
int op, l, r; ll x;
scanf("%d", &op);
if (op == 0) {
scanf("%d%d%llu", &l, &r, &x);
int lb = loc[l], rb = loc[r];
if (lb == rb) {
for (int i = l; i <= r; i++) x = H[i].calc(x);
printf("%llu\n", x);
} else {
x = sf[l].calc(x);
for (int i = lb + 1; i < rb; i++) x = F[i].calc(i);
x = pf[r].calc(x);
printf("%llu\n", x);
}
} else {
scanf("%d", &l);
read(H[l]);
rebuild(loc[l]);
}
}
return 0;
}
/*
3 1 1
1 4 0 0 51966
2 0 0 15 61 1 4095 46681
1 0 0 16 15
0 1 3 2023
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5976kb
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: 0
Accepted
time: 2ms
memory: 3876kb
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:
9487331362121050549 3906661590723083106 15757672015979182109 4975471776251039345 11503109206538591140 3763610618439604410
result:
ok 6 tokens
Test #3:
score: 0
Accepted
time: 17ms
memory: 4000kb
input:
1 20000 400 32 13 0 1721926083061553294 52 1 8951352260297008058 6 0 3180917732545757991 63 1 14978562500072226750 50 1 7331113732303115313 59 0 688182721924779475 12 0 16291922173168822489 61 0 16018198440613086698 8 0 12494084957448674305 7 0 2834422858291562646 42 1 10354539547309738529 28 0 2541...
output:
11827781865759498816 7454610526276185721 9581050724293785387 2177163806257271094 14004004964877510141 18073834598135159471 16966489063087641088 12289032565388413023 17823140805867698239 18104549908461644670 15570008264282957124 12400954982104000299 9842549278742638708 16535034933613060362 1561642006...
result:
ok 19600 tokens
Test #4:
score: -100
Wrong Answer
time: 2862ms
memory: 4316kb
input:
500 20000 400 32 3 0 9869926173615303101 39 1 11114680792832491178 54 1 3380955246053990760 31 0 16868042247314276464 26 0 5814925615581342395 30 1 1114053898154397400 46 1 9215698002668459992 38 1 12938485987410997250 58 0 8030873196223549640 0 0 16055471402053138912 47 1 16568729207788187629 63 0 ...
output:
15038074953522459312 10373498554439264746 5913085416774534533 13138593293404094284 17779091185932515087 9416316638936586738 457980708900208120 17325717000421583750 9973962510533285693 14945559959942587739 13076178073207603968 443306406691656062 4950009768812130591 1810406032145371210 430674413444631...
result:
wrong answer 1st words differ - expected: '9119093329811149961', found: '15038074953522459312'