Submission #340716

#	Time	Username	Problem	Language	Result	Execution time	Memory
340716		juggernaut	XOR (IZhO12_xor)	C++14	100 / 100	212 ms	24428 KiB

xor

#include<bits/stdc++.h>
using namespace std;
int par[250005],tree[250005*30][2],node,sub[250005*30],n,k;
void upd(int x){
	int now=0;
	for(int i=29;i>=0;i--){
		int bit=par[x]>>i&1;
		if(!tree[now][bit])
			tree[now][bit]=++node;
		now=tree[now][bit];
		sub[now]=max(sub[now],x);
	}
}
int get(int x){
	int now=0,val=0,res=0;
	for(int i=29;i>=0;i--){
		int bit=x>>i&1;
		int v1=tree[now][bit^1];
		int v0=tree[now][bit];
		if(v0&&v1){
			if(val+(1<<i)>=k)
				res=max(res,sub[v1]),now=v0;
			else
				val+=(1<<i),now=v1;
		}
		else if(v1){
			if(val+(1<<i)>=k)
				res=max(res,sub[v1]);
			else
				val+=(1<<i);
			now=v1;
		}
		else
			now=v0;
	}
	return res;
}
int main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++){
		scanf("%d",&par[i]);
		par[i]^=par[i-1];
	}
	int ans,mx=0;
	for(int i=n;i>=1;i--){
		upd(i);
		int res=get(par[i-1]);
		if(res&&res-i+1>=mx)mx=res-i+1,ans=i;
	}
	printf("%d %d",ans,mx);
}

Compilation message (stderr)

xor.cpp: In function 'int main()':
xor.cpp:39:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   39 |  scanf("%d%d",&n,&k);
      |  ~~~~~^~~~~~~~~~~~~~
xor.cpp:41:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   41 |   scanf("%d",&par[i]);
      |   ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 100 / 100