結果

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

ソースコード

diff # 

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


SHOW_PROGRESS = True
PROGRESS_THRESHOLD = 28
UNLIMITED = True
MAX_TESTCASES = 1000
MAX_N = 27
MAX_COST = 1e8
# Golden ratio (1+sqrt(5))/2 ≒ 1.618033988749895
PHI = math.sqrt(1.25) + 0.5  # Golden ratio


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]:
    """Generates Fibonacci sequence [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:
    """
    Checks if the given network is a sorting network.
    Operates in time complexity O(m * phi**n). phi is the golden ratio 1.618...
    """
    assert 2 <= n
    # Check the range of 0-indexed inputs
    assert all(0 <= a < b < n for a, b in net)
    # Number of comparators
    m = len(net)
    # Initial state is all '?' = indeterminate: not determined to be 0 or 1
    dict_queue: collections.defaultdict[tuple[int, int], int] = collections.defaultdict(int)
    dict_queue[((1 << n) - 1, (1 << n) - 1)] = 1
    # Record whether the comparator is ever used
    unused = []
    # Record unsorted positions
    unsorted_i = 0
    # Generate Fibonacci sequence
    fib = fib1(n)
    # Progress of search branches: from 0 to fib[n]
    progress = 0
    # show_progress
    show_progress = SHOW_PROGRESS and n >= PROGRESS_THRESHOLD
    for i, (a, b) in enumerate(net):
        dict_next: collections.defaultdict[tuple[int, int], int] = collections.defaultdict(int)
        unused_f = True
        for (z, o), c in dict_queue.items():
            if ((o >> a) & 1) == 0 or ((z >> b) & 1) == 0:
                dict_next[(z, o)] += c
            elif ((z >> a) & 1) == 1 and ((o >> b) & 1) == 1:
                unused_f = False
                qz, qo, z = z, (o ^ (1 << a) ^ (1 << b)), (z ^ (1 << b))
                if (qo & (qz >> 1)) == 0:
                    progress += c
                else:
                    dict_next[(qz, qo)] += c
                if (o & (z >> 1)) == 0:
                    progress += c
                else:
                    dict_next[(z, o)] += c
            else:
                unused_f = 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:
                    progress += c
                else:
                    dict_next[(z, o)] += c
        unused.append(unused_f)
        dict_queue = dict_next
        if show_progress:
            percent = i * 100 // m
            sys.stderr.write(f'{percent}%\r')
    for (z, o), c in dict_queue.items():
        unsorted_i |= (o & (z >> 1))
        progress += fib[(z & o).bit_count()] * c
    if show_progress:
        sys.stderr.write('\n')
    # Verify that the number of search branches matches the Fibonacci sequence value
    assert progress == fib[n]
    # If there are unsorted branches
    if unsorted_i != 0:
        unsorted = [((unsorted_i >> i) & 1) != 0 for i in range(n - 1)]
        return IsSortingNg(unsorted)
    # If all branches are sorted
    return IsSortingOk(unused)


def main():
    """Input and output processing for test cases"""
    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  # Computational cost of test cases
        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: Check if the given network is a sorting network
        is_sorting = is_sorting_network(n, cmps)
        print(is_sorting)  # Yes or No
        if is_sorting:
            # unused_cmp: Whether the comparator is unused (only if 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: Positions that may not be sorted (only if 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