QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#353752 | #8335. Fast Hash Transform | ucup-team004# | WA | 1ms | 3840kb | C++20 | 3.0kb | 2024-03-14 15:52:11 | 2024-03-14 15:52:13 |
Judging History
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'