maximum_xor_subarray_1655.cpp (1491B)
1 #include <algorithm> 2 #include <iostream> 3 #include <unordered_set> 4 #include <vector> 5 6 // First we compute the array a of cumulative xor starting from the 7 // first element (a[0] being set to 0 for convenience). Then we 8 // work bit by bit from the highest bit, building at each point 9 // an unordered set of the the available top-masked elements. We 10 // always try to find a full-mask, but when a bit is not available 11 // we store it in a the mask called "no". The reasoning is similar 12 // to finding a pair of elements in an array with a specified sum. 13 // The official solution uses a trie; it is more elegant and more 14 // efficient, but the idea is not too different. 15 16 unsigned bit(unsigned i) { return 1U << (i-1); } 17 18 bool no_bit(const std::vector<unsigned>& a, unsigned b) { 19 return std::ranges::none_of(a, [b](unsigned x){ return x & b; }); 20 } 21 22 bool pair_match( 23 const std::unordered_set<unsigned>& s, unsigned m, unsigned no) { 24 for (auto x : s) 25 if (s.contains(((~x)&m)^no)) 26 return true; 27 return false; 28 } 29 30 int main() { 31 size_t n; 32 std::cin >> n; 33 std::vector<unsigned> a(n+1); // Cumulative xor 34 a[0] = 0; 35 for (size_t i = 1; i <= n; i++) { 36 std::cin >> a[i]; 37 a[i] ^= a[i-1]; 38 } 39 unsigned i{32}, no{0}; 40 for ( ; i > 0 && no_bit(a, bit(i)); i--) 41 no |= bit(i); 42 i--; 43 std::unordered_set<unsigned> s; 44 for ( ; i > 0; i--) { 45 unsigned m = ~(bit(i) - 1); 46 s.clear(); 47 for (auto x : a) 48 s.insert(x & m); 49 if (!pair_match(s, m, no)) 50 no |= bit(i); 51 } 52 std::cout << ~no << "\n"; 53 }