Submission #896607

#TimeUsernameProblemLanguageResultExecution timeMemory
896607borisAngelovXOR (IZhO12_xor)C++17
100 / 100
80 ms96340 KiB
#include <bits/stdc++.h> using namespace std; const int maxn = 250005; const int maxBits = 29; const int inf = 1e9; int n, minXor; int a[maxn]; int pref[maxn]; int result = inf; struct Trie { struct Node { int children[2]; int minPos; Node() { children[0] = -1; children[1] = -1; minPos = inf; } }; Node trie[maxn * 32]; int root = 1; int nodeCnt = 1; void addNumber(int node, int number, int pos, int bit) { trie[node].minPos = min(trie[node].minPos, pos); if (bit == -1) { return; } bool hasBit = ((number & (1 << bit)) > 0); if (trie[node].children[hasBit] == -1) { trie[node].children[hasBit] = ++nodeCnt; } addNumber(trie[node].children[hasBit], number, pos, bit - 1); } void query(int node, int number, int pos, int bit, int currentXor) { if (bit == -1) { if (currentXor >= minXor) { //cout << "found " << trie[node].minPos << endl; result = min(result, trie[node].minPos); } return; } //cout << number << " " << pos << " " << bit << " :: " << currentXor << endl; bool hasBit = ((number & (1 << bit)) > 0); if (trie[node].children[hasBit] != -1 && currentXor + (1 << bit) - 1 >= minXor) { query(trie[node].children[hasBit], number, pos, bit - 1, currentXor); } if (trie[node].children[1 - hasBit] != -1) { query(trie[node].children[1 - hasBit], number, pos, bit - 1, currentXor + (1 << bit)); } } }; Trie trie; void fastIO() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); } int main() { fastIO(); cin >> n >> minXor; for (int i = 1; i <= n; ++i) { cin >> a[i]; } trie.addNumber(1, 0, 0, maxBits); int ans = 0; int from = 0; for (int i = 1; i <= n; ++i) { pref[i] = (pref[i - 1] ^ a[i]); result = inf; trie.query(1, pref[i], i, maxBits, 0); trie.addNumber(1, pref[i], i, maxBits); if (result != inf) { ++result; if (ans < i - result + 1) { ans = i - result + 1; from = result; } } } cout << from << ' ' << ans << endl; return 0; } /* 4 6 6 1 2 4 4 3 6 1 2 4 */
#Verdict Execution timeMemoryGrader output
Fetching results...