結果

問題 No.3047 Verification of Sorting Network
ユーザー 👑 Mizar
提出日時 2025-03-09 21:09:15
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 891 ms / 2,000 ms
コード長 6,501 bytes
コンパイル時間 390 ms
コンパイル使用メモリ 82,164 KB
実行使用メモリ 110,416 KB
最終ジャッジ日時 2025-03-09 21:09:46
合計ジャッジ時間 21,812 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 61
権限があれば一括ダウンロードができます

ソースコード

diff # 

"""
yukicoder Problem: Verify Sorting Network
"""
import functools
import math
import sys


SHOW_PROGRESS_THRESHOLD = 28
UNLIMITED = True
MAX_TESTCASES = 1000
MAX_N = 27
MAX_COST = 1e8


class IsSortingOk:
    """is_sorting_network Ok type"""
    def __init__(self, value: list[bool]):
        self.value = value

    def __bool__(self):
        return True

    def __str__(self):
        return 'Yes'

    def get_data(self):
        """get data value"""
        return self.value


class IsSortingNg:
    """is_sorting_network Ng type"""
    def __init__(self, value: list[bool]):
        self.value = value

    def __bool__(self):
        return False

    def __str__(self):
        return 'No'

    def get_error(self):
        """get error value"""
        return self.value


def fib1(n: int) -> list[int]:
    """フィボナッチ数列 [1,1,2,3,…,Fib(n+1)] を生成します。"""
    return functools.reduce(lambda x, _: x + [sum(x[-2:])], range(n), [1])


def is_sorting_network(n: int, net: list[tuple[int, int]]) -> IsSortingOk | IsSortingNg:
    """
    与えられたネットワークが sorting network であるかどうかを調べます。
    時間計算量 O(m * phi**n) で動作します。 phi は黄金比1.618...です。
    n は入力の数、 m は比較器の数です。
    ref: Hisayasu Kuroda. (1997). A proposal of Gap Decrease Sorting Network.
    Trans.IPS.Japan, vol.38, no.3, p.381-389.
    http://id.nii.ac.jp/1001/00013442/
    """
    assert 2 <= n
    # 0-indexed 入力の範囲を確認
    assert all(0 <= a < b < n for a, b in net)
    # 比較器の数
    m = len(net)
    # 初期状態はすべて '?' = 不定: 0 または 1 に決定されていない
    stack = [((1 << n) - 1, (1 << n) - 1, 0)]
    # 使われる事がある比較器かどうかを記録
    unused = [True] * m
    # ソートされない位置を記録
    unsorted_i = 0
    # レイヤー分割
    net_layers: list[list[tuple[int, int, int]]] = []
    net_remain: list[tuple[int, int, int]] = [(a, b, i) for i, (a, b) in enumerate(net)]
    while net_remain:
        layer_used = [False] * n
        layerx: list[tuple[int, int, int]] = []
        remain_next: list[tuple[int, int, int]] = []
        f = False
        for a, b, i in net_remain:
            if layer_used[a] or layer_used[b] or f:
                remain_next.append((a, b, i))
                f = True
            else:
                layerx.append((a, b, i))
            layer_used[a] = layer_used[b] = True
        net_layers.append(layerx)
        net_remain = remain_next
    assert [(a, b, i) for i, (a, b) in enumerate(net)] == [e for layer in net_layers for e in layer]
    # net_layers: list[list[tuple[int, int, int]]] = [[(a, b, i) for i, (a, b) in enumerate(net)]]
    # レイヤー毎に探索
    net_p: list[tuple[int, int, int]] = []
    for layer in net_layers:
        # net_p += layer
        net_p.extend(layer)
        net_plen = len(net_p)
        # 次のレイヤーのジョブの蓄積（重複した状態を除去）
        stack_nextlayer: set[tuple[int, int, int]] = set()
        while stack:
            z, o, i = stack.pop()
            while i < net_plen:
                a, b, j = net_p[i]
                i += 1
                if ((o >> a) & 1) == 0 or ((z >> b) & 1) == 0:
                    pass
                elif ((z >> a) & 1) == 0 or ((o >> b) & 1) == 0:
                    unused[j] = False
                    xz, xo = (((z >> a) ^ (z >> b)) & 1), (((o >> a) ^ (o >> b)) & 1)
                    z, o = (z ^ ((xz << a) | (xz << b))), (o ^ ((xo << a) | (xo << b)))
                    if (o & (z >> 1)) == 0:
                        break
                else:
                    unused[j] = False
                    qz, qo, z = z, (o ^ (1 << a) ^ (1 << b)), (z ^ (1 << b))
                    if (qo & (qz >> 1)) != 0:
                        stack.append((qz, qo, j))
                    if (o & (z >> 1)) == 0:
                        break
            else:
                stack_nextlayer.add((z, o, i))
        # 次のレイヤーのジョブを生成
        stack = list(stack_nextlayer)
        # 進捗表示
        if SHOW_PROGRESS_THRESHOLD <= n:
            percent = len(net_p) * 100 // len(net)
            sys.stderr.write(f'{percent}%\r')
    assert len(net_p) == len(net)
    if SHOW_PROGRESS_THRESHOLD <= n:
        sys.stderr.write('\n')
    # ソートされていない位置がある場合
    for z, o, i in stack:
        assert i == len(net)
        unsorted_i |= (o & (z >> 1))
    if unsorted_i != 0:
        unsorted = [((unsorted_i >> i) & 1) != 0 for i in range(n - 1)]
        return IsSortingNg(unsorted)
    # すべての分岐でソートされている場合
    return IsSortingOk(unused)


# 黄金比 (1+sqrt(5))/2 ≒ 1.618033988749895
PHI = math.sqrt(1.25) + 0.5  # 黄金比


def main():
    """テストケースの入出力処理"""
    t = int(sys.stdin.readline())
    assert t <= MAX_TESTCASES or UNLIMITED
    cost = 0
    for _ in range(t):
        n, m = map(int, sys.stdin.readline().split())
        assert 2 <= n <= MAX_N or UNLIMITED
        assert 1 <= m <= n * (n - 1) // 2 or UNLIMITED
        cost += m * PHI**n  # テストケースの計算量コスト
        assert cost <= MAX_COST or UNLIMITED
        # 1-indexed -> 0-indexed
        a = map(lambda x: int(x) - 1, sys.stdin.readline().split())
        b = map(lambda x: int(x) - 1, sys.stdin.readline().split())
        cmps: list[tuple[int, int]] = list(zip(a, b))
        assert len(cmps) == m
        assert all(0 <= a < b < n for a, b in cmps)
        # is_sorting: 与えられたネットワークが sorting network であるかどうか
        is_sorting = is_sorting_network(n, cmps)
        print(is_sorting)  # Yes or No
        if is_sorting:
            # unused_cmp: 使われない比較器かどうか (is_sorting=True の場合のみ)
            unused_cmp = is_sorting.get_data()
            assert len(unused_cmp) == m
            print(sum(unused_cmp))
            print(*map(lambda e: e[0] + 1, filter(lambda e: e[1], enumerate(unused_cmp))))
        else:
            # unsorted_pos: ソートされない可能性のある位置 (is_sorting=False の場合のみ)
            unsorted_pos = is_sorting.get_error()
            assert len(unsorted_pos) == n - 1
            print(sum(unsorted_pos))
            print(*map(lambda e: e[0] + 1, filter(lambda e: e[1], enumerate(unsorted_pos))))


main()
0