結果

問題 No.1652 XOR Inequalities
ユーザー Kiri8128
提出日時 2021-08-20 23:39:55
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,449 bytes
コンパイル時間 214 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 83,904 KB
最終ジャッジ日時 2024-10-14 07:45:31
合計ジャッジ時間 4,370 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 WA * 1
other TLE * 1 -- * 52
権限があれば一括ダウンロードができます

ソースコード

diff # 

from random import randrange
from time import time
def ra(a, b):
    la = a.bit_length()
    lb = b.bit_length()
    while 1:
        i = randrange(-1, min(la, lb))
        c = a ^ b if i < 0 else a ^ b ^ (1 << i) ^ randrange(1 << i)
        if chk(a, b, c):
            return c
    
    
def chk(a, b, c):
    if a ^ b <= c and b ^ c <= a and c ^ a <= b: return 1
    return 0

N = int(input())
NN = 1 << N
A = [int(a) for a in input().split()]
if A[0] < 0: A[0] = 0
if N == 1:
    if A[1] < 0: A[1] = 0
    print("Yes")
    print(*A)
    exit()

ng = 0
B = [max(a, 0) for a in A]
for i in range(NN):
    for j in range(NN):
        if B[i] ^ B[j] > B[i^j]:
            if A[i] >= 0 and A[j] >= 0 and A[i^j] >= 0:
                print("No")
                exit()
            ng += 1

sTime = time()
while ng and time() - sTime < 1.5:
    i = randrange(NN)
    if A[i] >= 0: continue
    j = 0
    while j == 0 or i == j:
        j = randrange(NN)
    c = ra(B[j], B[i^j])
    while 1:
        pre = 0
        new = 0
        for j in range(NN):
            if chk(c, B[j], B[i^j]) == 0:
                new += 10000 if A[j] >= 0 and A[i^j] >= 0 else 1
            if chk(B[i], B[j], B[i^j]) == 0:
                pre += 10000 if A[j] >= 0 and A[i^j] >= 0 else 1
        if new <= pre + 1:
            B[i] = c
            ng += new - pre
            break
        c = ra(B[j], B[i^j])

if ng:
    print("No")
else:
    print("Yes")
    print(*B)
0