結果

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

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    a = list(map(int, input[ptr:ptr+N]))
    ptr += N
    Q = int(input[ptr])
    ptr += 1
    b = list(map(int, input[ptr:ptr+Q]))
    ptr += Q

    mask = (1 << 60) - 1

    # Precompute the possible x after each step
    # We'll use a dictionary to track the minimal number of operation 2's needed to reach each x.
    dp = {0: 0}
    for ai in a:
        new_dp = {}
        for x in dp:
            cnt = dp[x]
            # Operation 1: x | ai
            x1 = x | ai
            if x1 in new_dp:
                if cnt < new_dp[x1]:
                    new_dp[x1] = cnt
            else:
                new_dp[x1] = cnt
            # Operation 2: (x | ai) ^ mask
            x2 = (x | ai) ^ mask
            if x2 in new_dp:
                if cnt + 1 < new_dp[x2]:
                    new_dp[x2] = cnt + 1
            else:
                new_dp[x2] = cnt + 1
        dp = new_dp.copy()

    # For each query, check if it exists in dp and output the minimal count
    results = []
    for bi in b:
        if bi in dp:
            results.append(dp[bi])
        else:
            results.append(-1)

    print('\n'.join(map(str, results)))

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