답안 #41330

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
41330	2018-02-16T12:33:50 Z	IvanC	XOR (IZhO12_xor)	C++14	100 / 100	225 ms	37436 KB

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

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.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	560 KB	Output is correct
4	Correct	2 ms	560 KB	Output is correct
5	Correct	11 ms	1448 KB	Output is correct
6	Correct	13 ms	1708 KB	Output is correct
7	Correct	13 ms	1912 KB	Output is correct
8	Correct	14 ms	2092 KB	Output is correct
9	Correct	70 ms	12524 KB	Output is correct
10	Correct	63 ms	13400 KB	Output is correct
11	Correct	63 ms	14008 KB	Output is correct
12	Correct	63 ms	14860 KB	Output is correct
13	Correct	60 ms	15556 KB	Output is correct
14	Correct	65 ms	16352 KB	Output is correct
15	Correct	63 ms	17208 KB	Output is correct
16	Correct	60 ms	17904 KB	Output is correct
17	Correct	186 ms	31560 KB	Output is correct
18	Correct	177 ms	33652 KB	Output is correct
19	Correct	182 ms	35428 KB	Output is correct
20	Correct	225 ms	37436 KB	Output is correct