From 96254947699986c59f0dc63d69fd4b76bd3ed43e Mon Sep 17 00:00:00 2001
From: Sebastiano Tronto <sebastiano@tronto.net>
Date: Mon, 6 Jul 2026 19:08:08 +0200
Subject: Initial commit

---
 .../maximum_xor_subarray_1655.cpp                  | 53 ++++++++++++++++++++++
 1 file changed, 53 insertions(+)
 create mode 100644 13_bitwise_operations/maximum_xor_subarray_1655.cpp

(limited to '13_bitwise_operations/maximum_xor_subarray_1655.cpp')

diff --git a/13_bitwise_operations/maximum_xor_subarray_1655.cpp b/13_bitwise_operations/maximum_xor_subarray_1655.cpp
new file mode 100644
index 0000000..9ae6564
--- /dev/null
+++ b/13_bitwise_operations/maximum_xor_subarray_1655.cpp
@@ -0,0 +1,53 @@
+#include <algorithm>
+#include <iostream>
+#include <unordered_set>
+#include <vector>
+
+// First we compute the array a of cumulative xor starting from the
+// first element (a[0] being set to 0 for convenience). Then we
+// work bit by bit from the highest bit, building at each point
+// an unordered set of the the available top-masked elements. We
+// always try to find a full-mask, but when a bit is not available
+// we store it in a the mask called "no". The reasoning is similar
+// to finding a pair of elements in an array with a specified sum.
+// The official solution uses a trie; it is more elegant and more
+// efficient, but the idea is not too different.
+
+unsigned bit(unsigned i) { return 1U << (i-1); }
+
+bool no_bit(const std::vector<unsigned>& a, unsigned b) {
+	return std::ranges::none_of(a, [b](unsigned x){ return x & b; });
+}
+
+bool pair_match(
+    const std::unordered_set<unsigned>& s, unsigned m, unsigned no) {
+	for (auto x : s)
+		if (s.contains(((~x)&m)^no))
+			return true;
+	return false;
+}
+
+int main() {
+	size_t n;
+	std::cin >> n;
+	std::vector<unsigned> a(n+1); // Cumulative xor
+	a[0] = 0;
+	for (size_t i = 1; i <= n; i++) {
+		std::cin >> a[i];
+		a[i] ^= a[i-1];
+	}
+	unsigned i{32}, no{0};
+	for ( ; i > 0 && no_bit(a, bit(i)); i--)
+		no |= bit(i);
+	i--;
+	std::unordered_set<unsigned> s;
+	for ( ; i > 0; i--) {
+		unsigned m = ~(bit(i) - 1);
+		s.clear();
+		for (auto x : a)
+			s.insert(x & m);
+		if (!pair_match(s, m, no))
+			no |= bit(i);
+	}
+	std::cout << ~no << "\n";
+}
-- 
cgit v1.3