結果

問題 No.3047 Verification of Sorting Network
ユーザー はにはに
提出日時 2025-03-06 02:08:12
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 4,678 bytes
コンパイル時間 439 ms
コンパイル使用メモリ 82,456 KB
実行使用メモリ 88,628 KB
最終ジャッジ日時 2025-03-06 02:08:21
合計ジャッジ時間 6,984 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 3
other WA * 61
権限があれば一括ダウンロードができます

ソースコード

diff # 

#!/usr/bin/env python3
import sys
input_data = sys.stdin.read().strip().split()
if not input_data:
    sys.exit(0)
it = iter(input_data)
T = int(next(it))
out_lines = []
# 各比較器が交換を起こしたかを記録するフラグ（全テストケース共通で更新）
# テストケース毎に個別に初期化する
for _ in range(T):
    N = int(next(it))
    M = int(next(it))
    # 読み込み：比較器 j の入力番号 A_j（1-indexed）
    A = [int(next(it)) for _ in range(M)]
    B = [int(next(it)) for _ in range(M)]
    # 今回のテストケース内で，各比較器 j (0-indexed)が少なくとも1度交換を起こしたか
    swapped = [False]*M

    # 各候補入力（「逆順入力」：左側に a 個の1，右側に N-a 個の0，
    # すなわち，入力列は 1^a 0^(N-a)；ただし  a=0, N は sorted となるので候補は a=1..N-1）
    # 各候補についてシミュレーションし，最終状態を記録する．
    # ここでは，入力・出力は 0‐1列を整数として表現する．
    # ただし，入力は「自然な順番」
    # すなわち，X[0]～X[N-1]（左から右）とし，sorted の状態は 0^(N-a) につづく 1^(a) となる．
    final_state = dict()  # key: a (1<= a <= N-1), value: 最終状態（整数）
    
    # 各候補についてシミュレーション
    for a in range(1, N):
        # candidate: 左側 a 個が 1，右側 N-a 個が 0
        # つまり，X[0..a-1] = 1, X[a..N-1] = 0.
        # 状態は整数 state で表し，X[i] は state の中で，左から i 番目の桁（0-indexed）とする．
        # 実際には，整数のビット表現では最上位ビットが X[0] に対応するようにする．
        state = ((1 << a) - 1) << (N - a)
        # シミュレーション（比較器は順に動作）
        for j in range(M):
            # 比較器 j は (A[j], B[j]) で与えられる（1-indexed，かつ A[j] < B[j]）
            # ここでは X[0]～X[N-1]（左から）とし，
            # 比較器は X[A[j]-1] と X[B[j]-1] を比較し，もし X[A[j]-1] > X[B[j]-1] なら交換
            ai = A[j] - 1
            bi = B[j] - 1
            # 状態 state の左から i 番目の値は，(state >> (N-1-i)) & 1 で得られる
            bit_a = (state >> (N - 1 - ai)) & 1
            bit_b = (state >> (N - 1 - bi)) & 1
            if bit_a == 1 and bit_b == 0:
                # 交換を記録
                swapped[j] = True
                # 交換：X[ai] と X[bi] の値を交換
                # state からは，該当するビットをそれぞれ変更する
                state = state - (1 << (N - 1 - ai)) + (1 << (N - 1 - bi))
        final_state[a] = state

    # sorted state（入力の popcount = a のとき）は，
    # 左側 (0～N-a-1) が 0，右側 (N-a～N-1) が 1
    # 整数で表すと，sorted_state = (1 << a) - 1 （ただし N 桁で考える）
    is_sorting = True
    unsorted_pop = []  # ソート失敗候補の a 値（＝候補の popcount）
    for a in range(1, N):
        target = (1 << a) - 1  # 下 a 桁が1，それ以外は0（N 桁表現）
        if final_state[a] != target:
            is_sorting = False
            unsorted_pop.append(a)
    if is_sorting:
        out_lines.append("Yes")
        # ソーティングネットワークの場合，交換が一度も起こらなかった比較器番号 j (1-indexed) をすべて出力
        never_swapped = [str(j+1) for j in range(M) if not swapped[j]]
        out_lines.append(str(len(never_swapped)))
        out_lines.append(" ".join(never_swapped))
    else:
        out_lines.append("No")
        # ネットワークがソートできない場合，
        # 各失敗候補の最終状態について，出力列 Y において Y[k] > Y[k+1] となり得る位置 k (1<= k <= N-1) を求める
        inv_set = set()
        # ※ 各候補は popcount a（a=unsorted_pop の候補）
        # 最終状態をリストに変換：Y[i] = (state >> (N-1-i)) & 1, i=0..N-1（i=0 が左端）
        for a in unsorted_pop:
            s = final_state[a]
            Y = [ (s >> (N-1-i)) & 1 for i in range(N) ]
            for i in range(N-1):
                if Y[i] > Y[i+1]:
                    # 問題文では，k 番目 (1<= k <= N-1) は，出力列の
                    # Y[k] と Y[k+1] の比較（すなわち，i = k-1 と k）
                    inv_set.add(i+1)
        inv_list = sorted(inv_set)
        out_lines.append(str(len(inv_list)))
        out_lines.append(" ".join(str(x) for x in inv_list))
        
sys.stdout.write("\n".join(out_lines))
0