Submission #343489

# Submission time Handle Problem Language Result Execution time Memory
343489 2021-01-04T01:27:23 Z nandonathaniel XOR (IZhO12_xor) C++14
100 / 100
573 ms 98180 KB
#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

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);
      |   ~~~~~^~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 32 ms 62956 KB Output is correct
2 Correct 32 ms 62956 KB Output is correct
3 Correct 32 ms 62956 KB Output is correct
4 Correct 35 ms 63212 KB Output is correct
5 Correct 49 ms 65152 KB Output is correct
6 Correct 54 ms 65132 KB Output is correct
7 Correct 53 ms 65260 KB Output is correct
8 Correct 57 ms 65388 KB Output is correct
9 Correct 204 ms 78644 KB Output is correct
10 Correct 197 ms 78644 KB Output is correct
11 Correct 198 ms 78544 KB Output is correct
12 Correct 227 ms 78516 KB Output is correct
13 Correct 218 ms 78644 KB Output is correct
14 Correct 201 ms 78772 KB Output is correct
15 Correct 206 ms 78516 KB Output is correct
16 Correct 202 ms 78516 KB Output is correct
17 Correct 573 ms 98180 KB Output is correct
18 Correct 565 ms 97968 KB Output is correct
19 Correct 567 ms 98044 KB Output is correct
20 Correct 558 ms 98044 KB Output is correct