結果

問題 No.283 スライドパズルと魔方陣
コンテスト
ユーザー qwewe
提出日時 2025-04-24 12:20:44
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,606 bytes
コンパイル時間 224 ms
コンパイル使用メモリ 82,640 KB
実行使用メモリ 76,744 KB
最終ジャッジ日時 2025-04-24 12:22:16
合計ジャッジ時間 4,881 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10 WA * 29
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def generate_magic_square(n):
    if n % 2 == 1:
        magic = [[0] * n for _ in range(n)]
        i, j = 0, n // 2
        for num in range(1, n*n + 1):
            magic[i][j] = num
            next_i, next_j = (i - 1) % n, (j + 1) % n
            if magic[next_i][next_j] != 0:
                i = (i + 1) % n
            else:
                i, j = next_i, next_j
        return magic
    else:
        return None

def count_inversions_flat(arr):
    inv_count = 0
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            if arr[i] != 0 and arr[j] != 0 and arr[i] > arr[j]:
                inv_count += 1
    return inv_count

def get_blank_pos(grid, n):
    for i in range(n):
        for j in range(n):
            if grid[i][j] == 0:
                return (i, j)
    return (-1, -1)

def main():
    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 = generate_magic_square(n)
    if magic is None:
        print("impossible")
        return

    target_n2 = n * n
    magic_pos = None
    for i in range(n):
        for j in range(n):
            if magic[i][j] == target_n2:
                magic_pos = (i, j)
                break
        if magic_pos:
            break

    original_flat = []
    original_zero_pos = get_blank_pos(grid, n)
    for i in range(n):
        for j in range(n):
            if grid[i][j] != 0:
                original_flat.append(grid[i][j])

    inv_original = count_inversions_flat(original_flat)

    magic_flat_excl_n2 = []
    for i in range(n):
        for j in range(n):
            if (i, j) != magic_pos:
                magic_flat_excl_n2.append(magic[i][j])

    inv_magic = count_inversions_flat(magic_flat_excl_n2)

    parity_diff = (inv_magic - inv_original) % 2

    blank_initial_row = original_zero_pos[0]
    blank_target_row = magic_pos[0]
    row_diff = blank_initial_row - blank_target_row
    row_parity_diff = abs(row_diff) % 2

    possible = False
    if n % 2 == 1:
        if parity_diff == 0:
            possible = True
    else:
        if parity_diff == row_parity_diff:
            possible = True

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

if __name__ == "__main__":
    main()
0