結果

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

ソースコード

diff # 

import sys

def is_magic_possible(n):
    if n == 1:
        return True
    if n % 2 == 1:
        return True
    if n % 4 == 0:
        return True
    return False

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 = (i - 1) % n
            next_j = (j + 1) % n
            if magic[next_i][next_j] != 0:
                i = (i + 1) % n
            else:
                i, j = next_i, next_j
        return magic
    elif n % 4 == 0:
        return None
    else:
        return None

def get_flattened(board, exclude_zero=True):
    flat = []
    for row in board:
        for num in row:
            if exclude_zero and num == 0:
                continue
            flat.append(num)
    return flat

def get_flattened_without_n2(magic, n_squared):
    flat = []
    for row in magic:
        for num in row:
            if num != n_squared:
                flat.append(num)
    return flat

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

def find_position(magic, n_squared):
    for i in range(len(magic)):
        for j in range(len(magic[i])):
            if magic[i][j] == n_squared:
                return (i, j)
    return (-1, -1)

def main():
    input = sys.stdin.read().split()
    idx = 0
    n = int(input[idx])
    idx += 1
    board = []
    for _ in range(n):
        row = list(map(int, input[idx:idx + n]))
        idx += n
        board.append(row)
    
    if not is_magic_possible(n):
        print("impossible")
        return
    
    magic = generate_magic_square(n)
    if magic is None:
        print("impossible")
        return
    
    n_squared = n * n
    
    current_flat = get_flattened(board, exclude_zero=True)
    t1 = count_inversion(current_flat)
    
    magic_flat_without_n2 = get_flattened_without_n2(magic, n_squared)
    t2 = count_inversion(magic_flat_without_n2)
    
    empty_row = -1
    for i in range(n):
        for j in range(n):
            if board[i][j] == 0:
                empty_row = i
                break
        if empty_row != -1:
            break
    
    magic_n2_row, magic_n2_col = find_position(magic, n_squared)
    
    possible = False
    if n % 2 == 1:
        if (t1 % 2) == (t2 % 2):
            possible = True
    else:
        row_diff = empty_row - magic_n2_row
        if (t1 - t2) % 2 == row_diff % 2:
            possible = True
    
    if possible:
        print("possible")
        for row in magic:
            print(' '.join(map(str, row)))
    else:
        print("impossible")

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