Cod sursa(job #3170182)

Utilizator vali2wdAdrian Valentin Nafornita vali2wd Data 16 noiembrie 2023 22:07:49
Problema Xor Max Scor 0
Compilator py Status done
Runda Arhiva de probleme Marime 2.19 kb
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)