結果

問題 No.283 スライドパズルと魔方陣
ユーザー Min_25
提出日時 2017-05-04 09:21:37
言語 PyPy2
(7.3.15)
結果
AC  
実行時間 103 ms / 2,000 ms
コード長 2,845 bytes
コンパイル時間 1,381 ms
コンパイル使用メモリ 76,408 KB
実行使用メモリ 78,592 KB
最終ジャッジ日時 2024-12-26 06:37:11
合計ジャッジ時間 8,198 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 39
権限があれば一括ダウンロードができます

ソースコード

diff # 

def solve():
  def magic_square(N):
    tab = [[0] * N for _ in range(N)]
    if N == 2:
      return tab
    if N & 1:
      o = N // 2
      for i in range(N):
        for j in range(N):
          tab[(i - o + j) % N][(i + o - j) % N] = i * N + j + 1
    elif N % 4 == 0:
      M = [1, 0, 0, 1]
      for i in range(N):
        for j in range(N):
          if (M[j & 3] ^ M[i & 3]) == 0:
            tab[i][j] = i * N + j + 1
          else:
            tab[i][j] = N * N - (i * N + j)
    else:
      base = magic_square(N // 2)
      base = [[4 * (c - 1) for c in line] for line in base]
      for i in range(N // 2):
        if i <= N // 4:
          D = [4, 1, 2, 3]
        elif i == N // 4 + 1:
          D = [1, 4, 2, 3]
        else:
          D = [1, 4, 3, 2]
        for j in range(N // 2):
          a = base[i][j]
          for k in range(2):
            for l in range(2):
              tab[2 * i + k][2 * j + l] = D[2 * k + l] + a
      M = N // 2 - 1
      tab[M][M], tab[M][M+1] = tab[M][M + 1], tab[M][M]
      tab[M+2][M], tab[M+2][M+1] = tab[M+2][M+1], tab[M+2][M]
    return tab

  def swap_count(perm):
    n = len(perm)
    visited = [0] * n
    ret = 0
    for i in range(n):
      if visited[i]: continue
      j = i
      visited[i] = True
      while perm[j] != i:
        j = perm[j]
        visited[j] = True
        ret += 1
    return ret

  def parity(N, tab):
    p1 = 0
    for i in range(N):
      for j in range(N):
        if tab[i][j] == N * N:
          p1 = (i ^ j) & 1
    perm = []
    for v in tab:
      perm.extend(v)
    perm = [c - 1 for c in perm]
    p2 = swap_count(perm)
    return (p1 ^ p2) & 1

  def confirm(N, tab):
    N2 = N * N
    s = N2 * (N2 + 1) // 2 // N
    for i in range(N):
      s2 = sum(tab[i][j] for j in range(N))
      assert(s == s2)
    for i in range(N):
      s2 = sum(tab[j][i] for j in range(N))
      assert(s == s2)
    s2 = sum(tab[i][i] for i in range(N))
    assert(s == s2)
    s2 = sum(tab[N - 1 - i][i] for i in range(N))
    assert(s == s2)
    return True

  import sys
  input = sys.stdin.readline

  ok = "possible"
  ng = "im" + ok

  while 1:
    try:
      N = int(input())
    except:
      break
    tab = []
    for i in range(N):
      tab += [ list(map(int, input().split())) ]

    if N == 1:
      print(ok)
      print(1)
    elif N == 2:
      print(ng)
    else:
      for i in range(N):
        for j in range(N):
          if tab[i][j] == 0:
            tab[i][j] = N * N

      mtab = magic_square(N)
      p1 = parity(N, tab)
      p2 = parity(N, mtab)
      if p1 != p2:
        if N & 1:
          mtab[0], mtab[-1] = mtab[-1], mtab[0]
        else:
          mtab = [v[::-1] for v in mtab]

      assert(p1 == parity(N, mtab))
      confirm(N, mtab)

      print(ok)
      for v in mtab:
        print(" ".join(map(str, v)))

solve()
0