# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
549807 | 2022-04-16T14:44:32 Z | racsosabe | XOR (IZhO12_xor) | C++14 | 13 ms | 29652 KB |
#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) 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 = -2; 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){ L = l + 1; R = i; } } insert(prefix, i); } printf("%d %d\n", L, R - L + 1); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 29652 KB | Output is correct |
2 | Incorrect | 13 ms | 29592 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |