Submission #549781

#	Time	Username	Problem	Language	Result	Execution time	Memory
549781		racsosabe	XOR (IZhO12_xor)	C++14	0 / 100	12 ms	30596 KiB

xor

#include<bits/stdc++.h>
using namespace::std;

const int E = 2;
const int L = 31;
const int SUML = 250000 * 31;

int n;
int x;
int nodes = 1;
int from[SUML];
int trie[E][SUML];

void insert(int val, int at){
	int pos = 0;
	for(int i = L - 1; i >= 0; i--){
		int nxt = (val >> i) & 1;
		if(trie[nxt][pos] == 0) trie[nxt][pos] = nodes++;
		pos = trie[nxt][pos];
		if(from[pos] == -1) from[pos] = at;
	}
}

int get(int val){
	int pos = 0;
	int res = -1;
	for(int i = L - 1; i >= 0; i--){
		int have = (val >> i) & 1;
		int digit = (x >> i) & 1;
		int nxt = digit ^ have;
		if(digit == 0 and trie[nxt ^ 1][pos]){
			if(res == -1 or res > from[trie[nxt ^ 1][pos]]) res = from[trie[nxt ^ 1][pos]];
		}
		if(!trie[nxt][pos]) break;
		pos = trie[nxt][pos];
	}
	return res;
}

int main(){
	scanf("%d %d", &n, &x);
	insert(0, 0);
	int prefix = 0;
	int L = -1, R = -1;
	memset(from, -1, sizeof from);
	for(int i = 1; i <= n; i++){
		int val;
		scanf("%d", &val);
		prefix ^= val;
		int l = get(prefix);
		if(~l){
			if(i - l > R - L + 1 or (i - l == R - L + 1 and l < L)){
				L = l + 1;
				R = i;
			}
		}
		insert(prefix, i);
	}
	printf("%d %d\n", L, R - L + 1);
	return 0;
}

Compilation message (stderr)

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

• Subtask 1: 0 / 100