結果

問題 No.1652 XOR Inequalities
ユーザー Kiri8128Kiri8128
提出日時 2021-08-20 23:41:01
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,468 bytes
コンパイル時間 609 ms
コンパイル使用メモリ 82,524 KB
実行使用メモリ 81,480 KB
最終ジャッジ日時 2024-04-22 08:38:17
合計ジャッジ時間 77,339 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 AC 42 ms
54,016 KB
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 AC 1,543 ms
76,928 KB
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 AC 1,544 ms
77,056 KB
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 AC 1,553 ms
77,320 KB
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 AC 1,550 ms
77,184 KB
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 AC 1,554 ms
77,220 KB
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 AC 1,552 ms
77,696 KB
testcase_31 WA -
testcase_32 WA -
testcase_33 WA -
testcase_34 WA -
testcase_35 AC 1,551 ms
77,180 KB
testcase_36 WA -
testcase_37 WA -
testcase_38 WA -
testcase_39 WA -
testcase_40 AC 1,552 ms
77,324 KB
testcase_41 WA -
testcase_42 WA -
testcase_43 AC 46 ms
60,416 KB
testcase_44 AC 48 ms
60,672 KB
testcase_45 AC 43 ms
54,144 KB
testcase_46 AC 46 ms
60,160 KB
testcase_47 AC 46 ms
60,672 KB
testcase_48 AC 143 ms
77,392 KB
testcase_49 WA -
testcase_50 AC 43 ms
54,400 KB
testcase_51 WA -
testcase_52 AC 180 ms
78,252 KB
testcase_53 WA -
testcase_54 WA -
testcase_55 WA -
権限があれば一括ダウンロードができます

ソースコード

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 time() - sTime < 1.5:
        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