Submission #1021005

#	Time	Username	Problem	Language	Result	Execution time	Memory
1021005		Minbaev	XOR (IZhO12_xor)	C++17	100 / 100	156 ms	24144 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(v1){
			if(val+(1<<i)>=k)
				res=max(res,sub[v1]);
				val+=(1<<i);
			now=v1;
		}
		else if(v0)
			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 get(int)':
xor.cpp:21:4: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   21 |    if(val+(1<<i)>=k)
      |    ^~
xor.cpp:23:5: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   23 |     val+=(1<<i);
      |     ^~~
xor.cpp: In function 'int main()':
xor.cpp:32:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |  scanf("%d%d",&n,&k);
      |  ~~~~~^~~~~~~~~~~~~~
xor.cpp:34:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |   scanf("%d",&par[i]);
      |   ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 100 / 100