Submission #41330

#	Time	Username	Problem	Language	Result	Execution time	Memory
41330		IvanC	XOR (IZhO12_xor)	C++14	100 / 100	225 ms	37436 KiB

xor

#include <bits/stdc++.h>
using namespace std;
const int MAXL = 31;
const int MAXN = 250010;
int Trie[MAXN*MAXL][2],maior[MAXN*MAXL],vetor[MAXN],resp1,resp2,N,K,triePtr,xoratorio;
int solve(int val){
	int ans = 0;
	int atual = 1;
	for(int i = MAXL - 1;i>=0;i--){
		int digito = 0;
		if(val & (1 << i)) digito = 1;
		int outro = 0;
		if(K & (1 << i)) outro = 1;
		if(outro == 1){
			atual = Trie[atual][digito ^ 1];
		}
		else{
			ans = max(ans, maior[Trie[atual][digito ^ 1]] );
			atual = Trie[atual][digito];
		}
	}
	ans = max(ans,maior[atual]);
	return ans;
}
void add(int val,int id){
	int atual = 1;
	for(int i = MAXL-1;i>=0;i--){
		int digito = 0;
		if(val & (1 << i)) digito = 1;
		if(Trie[atual][digito]){
			atual = Trie[atual][digito];
		}
		else{
			Trie[atual][digito] = ++triePtr;
			atual = Trie[atual][digito];
		}
		maior[atual] = max(maior[atual],id);
	}
}
int main(){
	triePtr = 1;
	scanf("%d %d",&N,&K);
	for(int i = 1;i<=N;i++) scanf("%d",&vetor[i]);
	add(xoratorio,N+1);
	for(int i = N;i>=1;i--){
		xoratorio ^= vetor[i];
		int davez = solve(xoratorio);
		if(davez - i >= resp1){
			resp1 = davez - i;
			resp2 = i;
		}
		add(xoratorio,i);
	}
	printf("%d %d\n",resp2,resp1);
	return 0;
}

Compilation message (stderr)

xor.cpp: In function 'int main()':
xor.cpp:42:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&N,&K);
                      ^
xor.cpp:43:47: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1;i<=N;i++) scanf("%d",&vetor[i]);
                                               ^

• Subtask 1: 100 / 100