結果

問題 No.283 スライドパズルと魔方陣
ユーザー qwewe
提出日時 2025-04-24 12:20:42
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,983 bytes
コンパイル時間 421 ms
コンパイル使用メモリ 82,596 KB
実行使用メモリ 60,472 KB
最終ジャッジ日時 2025-04-24 12:20:48
合計ジャッジ時間 5,946 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4 WA * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx += 1
    grid = []
    for _ in range(N):
        row = list(map(int, input[idx:idx+N]))
        grid.append(row)
        idx += N

    if N == 2:
        print("impossible")
        return

    if N == 1:
        print("possible")
        print(1)
        return

    magic = []
    if N == 3:
        magic = [
            [8, 1, 6],
            [3, 5, 7],
            [4, 9, 2]
        ]
    else:
        print("impossible")
        return

    target = []
    zero_pos = None
    for i in range(N):
        for j in range(N):
            if magic[i][j] == N*N:
                zero_pos = (i, j)
                break
        if zero_pos:
            break

    current = []
    target_linear = []
    for i in range(N):
        for j in range(N):
            if grid[i][j] != 0:
                current.append(grid[i][j])
            if magic[i][j] != N*N:
                target_linear.append(magic[i][j])

    if sorted(current) != sorted(target_linear):
        print("impossible")
        return

    def count_inversions(arr):
        inv = 0
        for i in range(len(arr)):
            for j in range(i+1, len(arr)):
                if arr[i] > arr[j]:
                    inv += 1
        return inv

    current_inv = count_inversions(current)
    target_inv = count_inversions(target_linear)

    current_zero_row = None
    for i in range(N):
        for j in range(N):
            if grid[i][j] == 0:
                current_zero_row = i

    target_zero_row = zero_pos[0]

    if N % 2 == 1:
        if (current_inv - target_inv) % 2 != 0:
            print("impossible")
            return
    else:
        diff_row = current_zero_row - target_zero_row
        if (current_inv - target_inv + diff_row) % 2 != 0:
            print("impossible")
            return

    print("possible")
    for row in magic:
        print(' '.join(map(str, row)))

main()
0