Submission #896595

#TimeUsernameProblemLanguageResultExecution timeMemory
896595borisAngelovXOR (IZhO12_xor)C++17
Compilation error
0 ms0 KiB
#include <bits/stdc++.h> using namespace std; const int maxn = 250005; const int maxBits = 30; int n, minXor; int a[maxn]; int pref[maxn]; int result = 1e9; struct Trie { struct Node { int children[2]; int minPos; Node() { children[0] = -1; children[1] = -1; minPos = 1e9; } }; Node trie[maxn * 32]; int root = 1; int nodeCnt = 1; void addNumber(int node, int number, int pos, int bit) { if (bit == -1) { trie[node].minPos = min(trie[node].minPos, pos); 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); trie[node].minPos = n + 1; if (trie[node].children[0] != -1) { trie[node].minPos = min(trie[node].minPos, trie[trie[node].children[0]].minPos); } if (trie[node].children[1] != -1) { trie[node].minPos = min(trie[node].minPos, trie[trie[node].children[1]].minPos); } } void query(int node, int number, int pos, int bit, int currentXor) { if (bit == -1) { return; } //cout << number << " " << pos << " " << bit << " :: " << currentXor << endl; if (currentXor >= minXor) { //cout << "found " << trie[node].minPos << endl; result = min(result, trie[node].minPos); return; } bool hasBit = ((number & (1 << bit)) > 0); if (trie[node].children[hasBit] != -1) { 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 = 1e9; trie.query(1, pref[i], i, maxBits, 0); trie.addNumber(1, pref[i], i, maxBits); if (result != 1e9) { ++result; if (ansLength < i - result + 1) { ansLength = i - result + 1; from = result; } } } cout << from << ' ' << ansLength << endl; return 0; } /* 4 6 6 1 2 4 4 3 6 1 2 4 */

Compilation message (stderr)

xor.cpp: In function 'int main()':
xor.cpp:133:17: error: 'ansLength' was not declared in this scope
  133 |             if (ansLength < i - result + 1)
      |                 ^~~~~~~~~
xor.cpp:141:28: error: 'ansLength' was not declared in this scope
  141 |     cout << from << ' ' << ansLength << endl;
      |                            ^~~~~~~~~
xor.cpp:117:9: warning: unused variable 'ans' [-Wunused-variable]
  117 |     int ans = 0;
      |         ^~~