Submission #549815

#	Time	Username	Problem	Language	Result	Execution time	Memory
549815		racsosabe	XOR (IZhO12_xor)	C++14	100 / 100	111 ms	45612 KiB

xor

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

const int E = 2;
const int L = 30;
const int SUML = 250000 * L + 5;

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){
			from[nodes] = at;
			trie[nxt][pos] = nodes++;
		}
		pos = trie[nxt][pos];
	}
}

int get(int val){
	int pos = 0;
	int res = -1;
	bool complete = true;
	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]){
			complete = false;
			break;
		}
		pos = trie[nxt][pos];
	}
	if(complete and (res == -1 or res > from[pos])) res = from[pos];
	return res;
}

int main(){
	scanf("%d %d", &n, &x);
	int prefix = 0;
	int L = -1, R = -2;
	memset(from, -1, sizeof from);
	insert(0, 0);
	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){
				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:48:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |  scanf("%d %d", &n, &x);
      |  ~~~~~^~~~~~~~~~~~~~~~~
xor.cpp:55:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |   scanf("%d", &val);
      |   ~~~~~^~~~~~~~~~~~

• Subtask 1: 100 / 100