結果

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

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    idx = 0
    N = int(data[idx])
    idx += 1
    a = list(map(int, data[idx:idx+N]))
    idx += N
    Q = int(data[idx])
    idx += 1
    b_list = list(map(int, data[idx:idx+Q]))
    
    mask = (1 << 60) - 1
    
    # Initialize current states
    current_states = {}
    current_states[(0, 0)] = 0
    
    for ai in a:
        next_states = {}
        for (y, f), cnt in current_states.items():
            # Apply operation 1
            if f == 0:
                y_op1 = y | ai
                f_op1 = 0
            else:
                y_op1 = y & (~ai)
                f_op1 = 1
            key = (y_op1, f_op1)
            if key not in next_states or cnt < next_states[key]:
                next_states[key] = cnt
            
            # Apply operation 2
            if f == 0:
                y_op2 = y | ai
                f_op2 = 1
            else:
                y_op2 = y & (~ai)
                f_op2 = 0
            new_cnt = cnt + 1
            key = (y_op2, f_op2)
            if key not in next_states or new_cnt < next_states[key]:
                next_states[key] = new_cnt
        current_states = next_states
        if not current_states:
            break
    
    # Process queries
    results = []
    for b in b_list:
        min_op2 = float('inf')
        # Check target1: (b, 0)
        if (b, 0) in current_states:
            min_op2 = min(min_op2, current_states[(b, 0)])
        # Check target2: (mask ^ b, 1)
        target2 = mask ^ b
        if (target2, 1) in current_states:
            min_op2 = min(min_op2, current_states[(target2, 1)])
        if min_op2 == float('inf'):
            results.append(-1)
        else:
            results.append(min_op2)
    
    print('\n'.join(map(str, results)))

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