結果
問題 | No.130 XOR Minimax |
ユーザー |
![]() |
提出日時 | 2022-12-10 23:07:43 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 557 ms / 5,000 ms |
コード長 | 863 bytes |
コンパイル時間 | 487 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 98,176 KB |
最終ジャッジ日時 | 2024-10-14 23:57:55 |
合計ジャッジ時間 | 8,607 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 |
ソースコード
N=int(input())A=[int(i) for i in input().split()]'''Y=0 できないY=2**30 できるmax(A)<Yにできるかどうかを判定するすべてのiについて、A_i xor X<YになるようなXが存在するかどうかを判定上位ビットから決める例12 18 1101100100100101101011011001001010111100'''def solve(B,k):'''全要素が2**k未満であるようなリストBについての答え'''ONE=[]ZERO=[]assert max(B)<(1<<k)if k==0:return 0if max(B)<(1<<(k-1)):return solve(B,k-1)if min(B)>=(1<<(k-1)):return solve([x^(1<<(k-1)) for x in B],k-1)for x in B:if (x>>(k-1))&1:ONE.append(x^(1<<(k-1)))else:ZERO.append(x)return (1<<(k-1))+min(solve(ONE,k-1),solve(ZERO,k-1))ans=solve(A,30)print(ans)