QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#352828 | #8335. Fast Hash Transform | installb | WA | 31ms | 505444kb | C++14 | 3.6kb | 2024-03-13 17:10:29 | 2024-03-13 17:10:30 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define M 64
using ull = unsigned long long;
struct Matrix{
bool A[M][M];
ull u[M],v[M];
void get(){
for(int i=0;i<M;i++)
for(int j=0;j<M;j++){
u[i] |= (ull)(A[i][j])<<j;
v[j] |= (ull)(A[i][j])<<i;
}
}
Matrix operator * (const Matrix &res)const{
Matrix ret;
for(int i=0;i<M;i++)
for(int j=0;j<M;j++)
ret.A[i][j]=__builtin_popcountll(u[i]^res.v[j])&1;
ret.get();
return ret;
}
Matrix operator + (const Matrix &res)const{
Matrix ret;
for(int i=0;i<M;i++)
for(int j=0;j<M;j++){
ret.A[i][j]=A[i][j]^res.A[i][j];
}
ret.get();
return ret;
}
ull operator & (const ull &res)const{
ull ret = 0;
for(int i=0;i<M;i++)
ret ^= ((ull)(__builtin_popcountll(u[i]^res)&1)<<i);
return ret;
}
Matrix(){
memset(A,0,sizeof(A));
}
};
struct Node{
Matrix k;
ull b;
Node(){}
Node(Matrix aa,ull bb):k(aa),b(bb){}
Node operator + (const Node &res)const{
return Node(k*res.k,(k&res.b)^b);
}
ull Ask(ull x){
return ((k&x)^b);
}
}Val[20005];
struct Seg{
struct TNODE{
int l,r;
Node v;
}tree[20005<<2];
#define fa tree[p]
#define lson tree[p<<1]
#define rson tree[p<<1|1]
int pos[20005];
void Up(int p){
fa.v = rson.v + lson.v;
}
void build(int l,int r,int p=1){
fa.l=l,fa.r=r;
if(l==r){
pos[l]=p;
fa.v=Val[l];
return;
}
int mid=l+r>>1;
build(l,mid,p<<1);
build(mid+1,r,p<<1|1);
Up(p);
}
void Update(int x){
int p = pos[x];
fa.v = Val[x];
for(int i=p>>1;i;i>>=1)Up(i);
}
ull Query(int l,int r,ull x,int p=1){
if(l==fa.l && r==fa.r)return fa.v.Ask(x);
int mid=fa.l+fa.r>>1;
if(r<=mid)return Query(l,r,x,p<<1);
else if(l>mid)return Query(l,r,x,p<<1|1);
else return Query(mid+1,r,Query(l,mid,x,p<<1),p<<1|1);
}
#undef fa
#undef lson
#undef rson
}T;
int m,s[20005];
ull A[20005],B;
int o[20005];
Matrix AND(ull p){
Matrix ret;
for(int i=0;i<64;i++)
if((1ull<<i)&p)ret.A[i][i]=1;
return ret;
}
Matrix Shift(int s){
Matrix ret;
for(int i=0;i<64;i++)
ret.A[i][(i-s+64)%64]=1;
return ret;
}
const ull BS = -1;
Node Trans(){
Matrix k;
ull b = 0;
for(int i=1;i<=m;i++){
if(o[i] == 1) k = k + (AND(A[i])*Shift(s[i]));
else k = k + (AND(A[i]^BS)*Shift(s[i]));
if(!o[i]) b ^= (AND(A[i])&BS);
}
b ^= B;
return Node(k,b);
}
int n,q,__C;
int main(){
cin>>n>>q>>__C;
for(int i=1;i<=n;i++){
scanf("%d",&m);
for(int j=1;j<=m;j++)
scanf("%d%d%llu",&s[j],&o[j],&A[j]);
scanf("%llu",&B);
Val[i] = Trans();
}
T.build(1,n);
while(q--){
int op;
scanf("%d",&op);
if(op==0){
int l,r;
ull x;
scanf("%d%d%llu",&l,&r,&x);
printf("%llu\n",T.Query(l,r,x));
}else{
int l;
scanf("%d",&l);
scanf("%d",&m);
for(int j=1;j<=m;j++)
scanf("%d%d%llu",&s[j],&o[j],&A[j]);
scanf("%llu",&B);
Val[l] = Trans();
T.Update(l);
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 31ms
memory: 505444kb
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:
51966 18446744073709551615 15 15
result:
wrong answer 1st words differ - expected: '64206', found: '51966'