QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#671655#8335. Fast Hash TransformbeidiaodajhtWA 1ms5860kbC++207.1kb2024-10-24 13:55:192024-10-24 13:55:19

Judging History

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

  • [2024-10-24 13:55:19]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5860kb
  • [2024-10-24 13:55:19]
  • 提交

answer

// #include<bits/stdc++.h>
// using namespace std;
// int n,b[1005];
// vector<pair<int,int> >ans;
// void solve(int l,int r){
// 	if(l==r) return ;
// 	int mid=(l+r)>>1;
// 	for(int i=1;i<=n;++i) if(b[i]>mid&&b[i]<=r) ans.emplace_back(make_pair(2,i));
// 	for(int i=l+1;i<=mid;++i) ans.emplace_back(make_pair(1,i));
// 	solve(l,mid);solve(mid+1,r);
// }
// int main(){
// 	scanf("%d",&n);
// 	for(int i=1;i<=n;++i) scanf("%d",&b[i]);
// 	solve(0,n);
// 	printf("%d\n",ans.size());
// 	for(auto a:ans) printf("%d %d\n",a.first,a.second);
// 	return 0;
// }
//A

// #include<bits/stdc++.h>
// #define M 100005
// using namespace std;
// int n,_4,_5,fa[M],Fa[M],dep[M],du[M],U,V;
// long long ans;
// vector<int> e[M];
// void dfs(int u,int fa){
// 	for(int v:e[u]) if(v!=fa){
// 		dep[v]=dep[u]+1;Fa[v]=u;
// 		dfs(v,u);
// 	}
// }
// void del(int x){
// 	_4-=(du[x]==4);_5-=(du[x]==5);
// 	du[x]--;
// 	_4+=(du[x]==4);_5+=(du[x]==5);
// }
// void add(int x){
// 	_4-=(du[x]==4);_5-=(du[x]==5);
// 	du[x]++;
// 	_4+=(du[x]==4);_5+=(du[x]==5);
// }
// int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
// int main(){
// 	scanf("%d",&n);
// 	for(int i=1;i<=n;++i) fa[i]=i;
// 	for(int i=1,u,v;i<=n;++i){
// 		scanf("%d%d",&u,&v);du[u]++;du[v]++;
// 		if(find(u)!=find(v)) e[u].emplace_back(v),e[v].emplace_back(u),fa[find(u)]=find(v);
// 		else U=u,V=v;
// 	}
// 	// printf("%d %d\n",U,V);
// 	for(int i=1;i<=n;++i) _4+=(du[i]==4),_5+=(du[i]==5);
// 	dfs(1,0);
// 	del(U);del(V);if(!_5) ans+=n-_4;add(U);add(V);
// 	while(U!=V){
// 		if(dep[V]>dep[U]) swap(U,V);
// 		del(U);del(Fa[U]);
// 		if(!_5) ans+=n-_4;
// 		add(U);add(Fa[U]);U=Fa[U];
// 	}
// 	printf("%lld",ans);
// 	return 0;
// }
//F

// #include<bits/stdc++.h>
// #define mod 1000000009
// using namespace std;
// long long m,k;
// int mi(int a,int b=mod-2){
// 	int ans=1;
// 	while(b){
// 		if(b&1) ans=1ll*ans*a%mod;
// 		b>>=1;a=1ll*a*a%mod;
// 	}
// 	return ans;
// }
// int main(){
// 	scanf("%lld%lld",&m,&k);
// 	long long nw=0,lf=0;
// 	for(int i=1;i<=k;++i){
// 		nw=(1ll*(lf+1)*m%mod+1ll*nw*(1+(i-1)*m)%mod)*mi((1ll*i*m+1)%mod)%mod;
// 		lf+=1ll*m*mi((1ll+1ll*i*(m-1))%mod)%mod;lf%=mod;
// 	}
// 	nw=nw*(1+1ll*k*m)%mod;
// 	printf("%lld",nw);	
// 	return 0;
// }
//L

// #include<bits/stdc++.h>
// #define N 31
// #define mod 1000000009
// using namespace std;
// int n,q,m,k,mi[60006],hsh[305][60006],Hsh[60006];
// char S[60006];
// long long ckk(int a,int b,int c){b--;
// 	if(a) return ((hsh[a][c]-1ll*hsh[a][b]*mi[c-b]%mod)%mod+mod)%mod;
// 	return ((Hsh[c]-1ll*Hsh[b]*mi[c-b]%mod)%mod+mod)%mod;
// }
// bool ck(int gu){
// 	int nw=0;
// 	for(int i=1;i<=k+1;++i){
// 		int l=nw+1,r=m,ans=nw;
// 		while(l<=r){
// 			int mid=(l+r)>>1;
// 			if(ckk(gu,nw+1,mid)==ckk(0,nw+1,mid)) l=mid+1,ans=mid;
// 			else r=mid-1;
// 		}
// 		nw=ans+1;
// 	}
// 	// printf("%d %d\n",gu,nw>m);
// 	return nw>m;
// }
// int main(){
// 	scanf("%d%d%d%d",&n,&q,&m,&k);
// 	mi[0]=1;
// 	for(int i=1;i<=m;++i) mi[i]=1ll*mi[i-1]*N%mod;
// 	for(int i=1;i<=n;++i){
// 		scanf(" %s",S+1);
// 		for(int j=1;j<=m;++j) hsh[i][j]=(1ll*hsh[i][j-1]*N+S[j]-'a'+1)%mod;
// 	}
// 	for(int i=1;i<=q;++i){
// 		scanf(" %s",S+1);
// 		for(int j=1;j<=m;++j) Hsh[j]=(1ll*Hsh[j-1]*N+S[j]-'a'+1)%mod;
// 		int ans=0;
// 		for(int j=1;j<=n;++j) ans+=ck(j);
// 		printf("%d\n",ans);
// 	}
// 	return 0;
// }

// #include<bits/stdc++.h>
// #define M 100005
// using namespace std;
// int T,n,dep[M],fa[M][25],a[M],m,al[M],Dep[M];
// vector<int> e[M];
// void pre(int u,int fa){
// 	::fa[u][0]=fa;
// 	for(int i=1;(1<<i)<=dep[u];++i) ::fa[u][i]=::fa[::fa[u][i-1]][i-1];
// 	for(int v:e[u]) if(v!=fa){
// 		dep[v]=dep[u]+1;
// 		pre(v,u);al[u]+=al[v];
// 	}
// 	if(u<=m) al[u]=1;
// }
// int lca(int x,int y){
// 	if(dep[x]<dep[y]) swap(x,y);
// 	for(int i=dep[x]-dep[y];i;i-=(i&(-i))) x=fa[x][__builtin_ctz(i)];
// 	if(x==y) return x;
// 	for(int i=20;~i;--i) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
// 	return fa[x][0];
// }
// void dfs(int u,int fa){
// 	for(int v:e[u]) if(v!=fa){
// 		Dep[v]=Dep[u]+(al[u]!=1);
// 		dfs(v,u);
// 		if(!a[u]) a[u]=a[v];
// 		else a[u]=lca(a[u],a[v]);
// 	}
// 	if(u<=m) a[u]=(u==m?0:u)+1;
// }
// bool solve(){
// 	scanf("%d%d",&n,&m);
// 	for(int i=1,u,v;i<n;++i){
// 		scanf("%d%d",&u,&v);
// 		e[u].emplace_back(v);e[v].emplace_back(u);
// 	}
// 	pre(n,0);dfs(n,0);
// 	// for(int i=1;i<=n;++i) printf("%d ",a[i]);
// 	for(int i=1;i<=n;++i) e[i].clear();
// 	for(int i=1;i<=n;++i) for(int j=0;j<=20;++j) fa[i][j]=0;
// 	for(int i=1;i<=n;++i) if(Dep[a[i]]<Dep[i]) return 0;
// 	return 1;
// }
// int main(){
// 	scanf("%d",&T);
// 	while(T--){
// 		if(solve()) printf("Doddle\n");
// 		else printf("Tie\n");
// 		for(int i=1;i<=n;++i) Dep[i]=al[i]=dep[i]=a[i]=0;
// 	}
// 	return 0;
// }
//D

// #pragma GCC optimize(2)
#include<bits/stdc++.h>
#define M 20005
#define mid ((l+r)>>1)
using namespace std;
int n,q,c,m,s[M],o[M];
unsigned long long B,A[M];
struct node{
	unsigned long long a[70]; 
	bool x[70];
}a[M],sm[M<<2];
node add(node b,node a){
	node ans({});
	for(int i=0;i<=63;++i){
		ans.x[i]=a.x[i];
		for(int j=a.a[i];j;j-=j&-j) 
			ans.a[i]^=b.a[__builtin_ctzll(j)],ans.x[i]^=b.x[__builtin_ctzll(j)];
	}
	return ans;
}
node cj(){
	node ans({});
	for(int i=0;i<=63;++i){
		ans.x[i]=((B>>i)&1);
		for(int j=1;j<=m;++j){
			if(((A[j]>>i)&1)&&o[j]==0){ans.x[i]^=1;continue;}
			if((!((A[j]>>i)&1))&&o[j]==1) continue;
			if(i>=s[j]) ans.a[i]^=(1ll<<(i-s[j]));
			else ans.a[i]^=(1ll<<(64+i-s[j]));
		}
	}
	return ans;
}
void build(int p,int l,int r){
	if(l==r){sm[p]=a[l];return ;}
	build(p<<1,l,mid);build(p<<1|1,mid+1,r);
	sm[p]=add(sm[p<<1],sm[p<<1|1]);
}
node ck(int p,int l,int r,int L,int R){
	if(L<=l&&r<=R) return sm[p];
	if(L>mid) return ck(p<<1|1,mid+1,r,L,R);
	if(R<=mid) return ck(p<<1,l,mid,L,R);
	return add(ck(p<<1,l,mid,L,R),ck(p<<1|1,mid+1,r,L,R));
}
void cg(int p,int l,int r,int pos){
	if(l==r){sm[p]=a[l];return;}
	if(pos<=mid) cg(p<<1,l,mid,pos);
	else cg(p<<1|1,mid+1,r,pos);
	sm[p]=add(sm[p<<1],sm[p<<1|1]);
}
void print(node a){
	for(int i=0;i<=63;++i) printf("%llu ",a.a[i]);
	printf("\n");
	for(int i=0;i<=63;++i) printf("%d ",a.x[i]);
	printf("\n");
}
int main(){
	scanf("%d%d%*d",&n,&q);
	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);
		a[i]=cj();
		// print(a[i]);
	}
	build(1,1,n);
	int op,i,l,r;
	unsigned long long x;
	while(q--){
		scanf("%d",&op);
		if(op){
			scanf("%d",&i);
			scanf("%d",&m);
			for(int j=1;j<=m;++j) scanf("%d%d%llu",&s[j],&o[j],&A[j]);
			scanf("%llu",&B);
			a[i]=cj();
			cg(1,1,n,i);
		}
		else{
			scanf("%d%d%llu",&l,&r,&x);
			node ans=ck(1,1,n,l,r);
			// print(ans);
			unsigned long long as=0;
			for(int i=0;i<=63;++i){
				bool nw=ans.x[i];
				nw^=((__builtin_popcountll(ans.a[i]&x))&1);
				if(nw) as|=(1ll<<i);
			}
			printf("%llu\n",as);
		}
	}
	return 0;
}
// 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
// 0 1 3 2023

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 5860kb

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

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:

9094089996805286074
7594268215574580721
3669892412548376452
6670126286539881910
4821519404190863710
3763610618439604410

result:

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