Submission #549815

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
549815	2022-04-16T15:04:24 Z	racsosabe	XOR (IZhO12_xor)	C++14	100 / 100	111 ms	45612 KB

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

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

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	29652 KB	Output is correct
2	Correct	11 ms	29624 KB	Output is correct
3	Correct	14 ms	29644 KB	Output is correct
4	Correct	14 ms	29652 KB	Output is correct
5	Correct	16 ms	30036 KB	Output is correct
6	Correct	19 ms	30216 KB	Output is correct
7	Correct	17 ms	30124 KB	Output is correct
8	Correct	21 ms	30164 KB	Output is correct
9	Correct	42 ms	36940 KB	Output is correct
10	Correct	43 ms	36956 KB	Output is correct
11	Correct	43 ms	36940 KB	Output is correct
12	Correct	43 ms	37000 KB	Output is correct
13	Correct	43 ms	36996 KB	Output is correct
14	Correct	43 ms	37044 KB	Output is correct
15	Correct	42 ms	36984 KB	Output is correct
16	Correct	45 ms	37048 KB	Output is correct
17	Correct	108 ms	45612 KB	Output is correct
18	Correct	107 ms	45516 KB	Output is correct
19	Correct	111 ms	45608 KB	Output is correct
20	Correct	110 ms	45536 KB	Output is correct