Submission #343489

#	Time	Username	Problem	Language	Result	Execution time	Memory
343489		nandonathaniel	XOR (IZhO12_xor)	C++14	100 / 100	573 ms	98180 KiB

xor

#include<bits/stdc++.h>
using namespace std;
const int LOG=30,RAND=8e6+5;
int child[2][RAND],anak[RAND],parent[RAND];
unordered_map<int,int> sudah,ujung;
int s,ret,n,k,x,i;
 
void ngisi(int tmp,int pos){
	if(pos==-1)return;
	if(child[0][tmp]!=-1 && child[1][tmp]!=-1){
		anak[tmp]=min(anak[child[0][tmp]],anak[child[1][tmp]]);
	}
	else if(child[1][tmp]!=-1){
		anak[tmp]=anak[child[1][tmp]];
	}
	else if(child[0][tmp]!=-1){
		anak[tmp]=anak[child[0][tmp]];
	}
	ngisi(parent[tmp],pos-1);
}
 
void insert(int tmp,int pos){
	if(pos==-1){
		sudah[s]=tmp;
		return;
	}
	int now=s&(1<<pos);
	if(now>0)now=1;
	if(child[now][tmp]==-1){
		ret++;
		child[now][tmp]=ret;
		parent[child[now][tmp]]=tmp;
		anak[child[now][tmp]]=i+1;
	}
	insert(child[now][tmp],pos-1);
}

int search(int tmp,int pos){
	if(child[0][tmp]==-1 && child[1][tmp]==-1)return RAND;
	int bitk=k&(1<<pos),bits=s&(1<<pos);
	if(bitk>0)bitk=1;
	if(bits>0)bits=1;
	int res=RAND;
	if(bitk==1){
		if(bits==1){
			if(child[0][tmp]!=-1){
				res=min(res,search(child[0][tmp],pos-1));
			}
		}
		else{
			if(child[1][tmp]!=-1){
				res=min(res,search(child[1][tmp],pos-1));
			}
		}
	}
	else{
		if(bits==0){
			if(child[0][tmp]!=-1){
				res=min(res,search(child[0][tmp],pos-1));
			}
			if(child[1][tmp]!=-1){
				res=min(res,anak[child[1][tmp]]);
			}
		}
		else{
			if(child[1][tmp]!=-1){
				res=min(res,search(child[1][tmp],pos-1));
			}
			if(child[0][tmp]!=-1){
				res=min(res,anak[child[0][tmp]]);
			}
		}
	}
	return res;
}

int main(){
	memset(child,-1,sizeof(child));
	scanf("%d%d",&n,&k);
	anak[s]=1;
	insert(0,LOG-1);
	ujung[s]=1;
	int pjg=-1,awal;
	for(i=1;i<=n;i++){
		scanf("%d",&x);
		s^=x;
		int L=search(0,LOG-1);
		if(ujung.count(k^s))L=min(L,ujung[k^s]);
		if(L>=1 && L<=i){
			if(i-L+1>pjg){
				pjg=i-L+1;
				awal=L;
			}
		}
		if(!sudah.count(s)){
			insert(0,LOG-1);
		}
		ngisi(sudah[s],LOG-1);
		if(!ujung.count(s))ujung[s]=i+1;
	}
	printf("%d %d\n",awal,pjg);
	return 0;
}

Compilation message (stderr)

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

• Subtask 1: 100 / 100