Submission #338524

#	Time	Username	Problem	Language	Result	Execution time	Memory
338524		juggernaut	XOR (IZhO12_xor)	C++14	100 / 100	175 ms	22508 KiB

xor

#include "bits/stdc++.h"
#define MAXN 250009
using namespace std;
int p[MAXN],n,X;
int tree[MAXN*30][2],sub[MAXN*30],nd;
void add(int x,int ind){
	int now=0;
	for(int i=29;i>=0;i--){
		int bit=x>>i&1;
		if(tree[now][bit])
			now=tree[now][bit];
		else{
			tree[now][bit]=++nd;
			sub[nd]=n+1;
			now=tree[now][bit];
		}
		sub[now]=min(sub[now],ind);
	}
}
int get(int i,int x,int now,int cur){
	if(cur>=X)
		return sub[now];
	if(i<0 or cur+(1<<i+1)-1<X)
		return n+1;
	int bit=x>>i&1,ret=n+1;
	for(int j=0;j<2;j++)
		if(tree[now][j])
			ret=min(ret,get(i-1,x,tree[now][j],cur+(j!=bit)*(1<<i)));
	return ret;
}	
int main(){
    //freopen("file.in", "r", stdin);
    scanf("%d%d",&n,&X);
    for(int i=1;i<=n;i++){
    	scanf("%d",p+i);
    	p[i]^=p[i-1];
    }
    int a=1,b=1;
    for(int i=1;i<=n;i++){
    	add(p[i-1],i);
		int l=get(29,p[i],0,0);
		if(i-l>b-a)
			a=l,b=i;	
    }
    printf("%d %d\n",a,b-a+1);
	return 0;
}

Compilation message (stderr)

xor.cpp: In function 'int get(int, int, int, int)':
xor.cpp:23:21: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   23 |  if(i<0 or cur+(1<<i+1)-1<X)
      |                    ~^~
xor.cpp: In function 'int main()':
xor.cpp:33:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   33 |     scanf("%d%d",&n,&X);
      |     ~~~~~^~~~~~~~~~~~~~
xor.cpp:35:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   35 |      scanf("%d",p+i);
      |      ~~~~~^~~~~~~~~~

• Subtask 1: 100 / 100