結果

問題 No.1296 OR or NOR
ユーザー qwewe
提出日時 2025-05-14 13:24:14
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,443 bytes
コンパイル時間 153 ms
コンパイル使用メモリ 82,592 KB
実行使用メモリ 641,864 KB
最終ジャッジ日時 2025-05-14 13:25:44
合計ジャッジ時間 8,171 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 2 MLE * 1 -- * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    N = int(sys.stdin.readline())
    A_values = list(map(int, sys.stdin.readline().split()))
    Q_count = int(sys.stdin.readline())
    B_queries = list(map(int, sys.stdin.readline().split()))

    ALL_ONES = (1 << 60) - 1

    # dp stores: value -> min_op2_count
    # Initialize with x=0, 0 op2s used
    dp = {0: 0}

    for i in range(N):
        a_i = A_values[i]
        new_dp = {} 
        
        # Iterate over states reachable in the previous step
        for x_prev, k_prev in dp.items():
            # Operation 1: x = x_prev OR a_i
            x_op1 = x_prev | a_i
            k_op1 = k_prev
            
            # If x_op1 is new or we found a path with fewer op2s
            if x_op1 not in new_dp or k_op1 < new_dp[x_op1]:
                new_dp[x_op1] = k_op1

            # Operation 2: x = NOT (x_prev OR a_i)
            intermediate_or_val = x_prev | a_i
            x_op2 = ALL_ONES ^ intermediate_or_val # Bitwise NOT over 60 bits
            k_op2 = k_prev + 1
            
            # If x_op2 is new or we found a path with fewer op2s
            if x_op2 not in new_dp or k_op2 < new_dp[x_op2]:
                new_dp[x_op2] = k_op2
        
        dp = new_dp # Update dp table for the current step

    results = []
    for b_q in B_queries:
        results.append(str(dp.get(b_q, -1)))
    
    sys.stdout.write("\n".join(results) + "\n")

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