Pagini recente » Cod sursa (job #273085) | Cod sursa (job #2792445) | Cod sursa (job #1227873) | Cod sursa (job #594538) | Cod sursa (job #3170184)
import sys
import gc
sys.stdout = open("xormax.out","w")
class TrieNode:
def __init__(self):
self.left_right = [None, None]
self.index = -1 # index cu semnificatia i-ului din explicatie; ai xor ... xor aj
def insert(trie: TrieNode, numberAsInt: int, index: int, trieDepth: int = 20):
# convert int to binary
numberAsBinary = bin(numberAsInt)[2:]
zerosToInsert = trieDepth - len(numberAsBinary)
while zerosToInsert > 0:
if trie.left_right[0] is None:
trie.left_right[0] = TrieNode()
trie = trie.left_right[0]
zerosToInsert -= 1
while len(numberAsBinary) > 0:
if int(numberAsBinary[0]) == 0:
if trie.left_right[0] is None:
trie.left_right[0] = TrieNode()
trie = trie.left_right[0]
else:
if trie.left_right[1] is None:
trie.left_right[1] = TrieNode()
trie = trie.left_right[1]
numberAsBinary = numberAsBinary[1:]
trie.index = index
def partial_xor_query(trie: TrieNode, numberAsInt: int, trieDepth: int = 20):
answer = 0
for bit in range(trieDepth, 0, -1):
curr_bit = bool(numberAsInt & (1 << (bit - 1)))
if trie.left_right[(not curr_bit)] is None:
trie = trie.left_right[curr_bit]
else:
trie = trie.left_right[(not curr_bit)]
answer |= (1 << (bit - 1))
return [answer, trie.index]
if __name__ == "__main__":
file = open("xormax.in", "r")
n = int(file.readline())
arr = list(map(int, file.readline().split()))
trie = TrieNode()
insert(trie, 0, -1, 20)
xor_sum = 0
best_start_idx = 0
max_val = 0
best_end_idx = 0
for idx, value in enumerate(arr):
xor_sum = xor_sum ^ value
query, start_idx = partial_xor_query(trie, xor_sum, 20)
max_val, best_start_idx, best_end_idx = [max_val, best_start_idx, best_end_idx] if max_val > query else [query, start_idx, idx]
# max_val, best_start_idx = [query, start_idx] if query > value else [value, idx - 1]
insert(trie, xor_sum, idx, 20)
print(max_val, best_start_idx + 2, best_end_idx + 1)