Участник:Berkut.kiu/ChefAndPie

Материал из DISCOPAL
Перейти к: навигация, поиск

задача: https://www.codechef.com/problems/CHXORR посылка: https://www.codechef.com/viewsolution/45310409

Мой алгоритм работает за O(N^2 * log(MAX)), где MAX - максимальный элемент в массиве

Код проходит не все тайм лимиты потому что скорее всего задача создана под C++(аналогичный алгоритм с деревом на плюсах заходит без тайм лимитов).

from collections import defaultdict
import numpy as np
 
class Trie:
    def __init__(self):
        self.root = defaultdict()
 
    def insert(self, word):
        current = self.root
        for letter in word:
            current = current.setdefault(letter, {})
        current.setdefault("_end")
 
    def search(self, word):
        current = self.root
        for letter in word:
            if letter not in current:
                return False
            current = current[letter]
        return True
 
def norm_bin(max_m, x):
    length = len(bin(max_m)[2:])
    x = bin(x)[2:]
    zeros = '0' * (length - len(x))
    return zeros + x
 
def max_xor_3(m):
    if len(m) == 3:
        return m[0] ^ m[1] ^ m[2]
    max_m = max(m)
    max_xor = 0
    for i in range(len(m) - 1):
        for j in range(i + 1, len(m)):
            tree = Trie()
            for k in range(len(m)):
                if k != i and k != j:
                    tree.insert(norm_bin(max_m, m[k]))
            w = m[i] ^ m[j]
            w_bin = norm_bin(max_m, w)
            z = ''
            for char in w_bin:
                char_obr = str((int(char) + 1) % 2)
                if tree.search(z + char_obr):
                    z += char_obr
                else:
                    z += char
            xor = w ^ (sum(int(c) * (2 ** i) for i, c in enumerate(z[::-1])))
            if xor > max_xor:
                max_xor = xor
 
    return max_xor
 
n = int(input())
for i in range(n):
    size = int(input())
    m = list(map(int,input().split()))
    m = np.array(m)
    print(max_xor_3(m))