結果

問題 No.1296 OR or NOR
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 14:34:11
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,250 bytes
コンパイル時間 188 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 666,228 KB
最終ジャッジ日時 2025-06-12 14:34:20
合計ジャッジ時間 7,134 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 2 MLE * 1 -- * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    ptr = 0
    N = int(data[ptr])
    ptr += 1
    a = list(map(int, data[ptr:ptr + N]))
    ptr += N
    Q = int(data[ptr])
    ptr += 1
    b = list(map(int, data[ptr:ptr + Q]))
    
    MOD = (1 << 60) - 1
    
    dp = {0: 0}  # x: min_operations
    
    for ai in a:
        new_dp = {}
        for x_prev, cnt_prev in dp.items():
            # Operation 1
            x_new = x_prev | ai
            if x_new in new_dp:
                if cnt_prev < new_dp[x_new]:
                    new_dp[x_new] = cnt_prev
            else:
                new_dp[x_new] = cnt_prev
            
            # Operation 2
            x_or = x_prev | ai
            x_new = MOD - x_or
            cnt_new = cnt_prev + 1
            if x_new in new_dp:
                if cnt_new < new_dp[x_new]:
                    new_dp[x_new] = cnt_new
            else:
                new_dp[x_new] = cnt_new
        
        dp = new_dp
    
    # Prepare the answer for each query
    res = []
    for bi in b:
        if bi in dp:
            res.append(str(dp[bi]))
        else:
            res.append("-1")
    
    print('\n'.join(res))

if __name__ == "__main__":
    main()
0