結果

問題 No.2986 Permutation Puzzle
ユーザー ID 21712
提出日時 2025-02-23 00:53:31
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
WA  
実行時間 -
コード長 2,182 bytes
コンパイル時間 1,106 ms
コンパイル使用メモリ 12,544 KB
実行使用メモリ 10,752 KB
最終ジャッジ日時 2025-02-23 00:53:36
合計ジャッジ時間 3,893 ms
ジャッジサーバーID
(参考情報)
judge2 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample WA * 4
other WA * 40
権限があれば一括ダウンロードができます

ソースコード

diff #

# this code generate by ChatGPT

import sys

def find_permutation_order(original, modified):
    """
    original: 1 から N の順列
    modified: 並び替えられた順列
    どの位置に移動したかを表す順列を返す
    """
    N = len(original)
    perm = [0] * N
    pos = {value: idx for idx, value in enumerate(original)}  # 各値の元の位置

    for i in range(N):
        perm[i] = pos[modified[i]] + 1  # 1-based index
    return perm

def apply_permutation(matrix, perm, axis):
    """
    matrix の行または列を perm に従って並び替える
    axis = 0 (行を並び替え)
    axis = 1 (列を並び替え)
    """
    N = len(matrix)
    new_matrix = [[0] * N for _ in range(N)]
    
    if axis == 0:  # 行の並び替え
        for i in range(N):
            new_matrix[i] = matrix[perm[i] - 1]  # 1-based index
    else:  # 列の並び替え
        for i in range(N):
            for j in range(N):
                new_matrix[i][j] = matrix[i][perm[j] - 1]  # 1-based index
    
    return new_matrix

def solve(N, K, A, B):
    operations = []
    
    # 各行・各列の順列を取得
    row_permutations = [find_permutation_order(B[i], A[i]) for i in range(N)]
    col_permutations = [find_permutation_order([B[i][j] for i in range(N)], [A[i][j] for i in range(N)]) for j in range(N)]
    
    # 逆操作を適用
    for i in range(N):
        if row_permutations[i] != list(range(1, N + 1)):  # 元の順序でないなら
            operations.append(f"R {i + 1}")
            B = apply_permutation(B, row_permutations[i], axis=0)
    
    for j in range(N):
        if col_permutations[j] != list(range(1, N + 1)):  # 元の順序でないなら
            operations.append(f"C {j + 1}")
            B = apply_permutation(B, col_permutations[j], axis=1)

    # 出力
    print(len(operations))
    for op in operations:
        print(op)

if __name__ == "__main__":
    # 入力
    N, K = map(int, sys.stdin.readline().split())
    A = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
    B = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

    # 解く
    solve(N, K, A, B)
0