結果

問題 No.283 スライドパズルと魔方陣
ユーザー Min_25Min_25
提出日時 2017-05-04 09:21:37
言語 PyPy2
(7.3.15)
結果
AC  
実行時間 98 ms / 2,000 ms
コード長 2,845 bytes
コンパイル時間 1,307 ms
コンパイル使用メモリ 77,724 KB
実行使用メモリ 79,752 KB
最終ジャッジ日時 2023-08-27 02:03:41
合計ジャッジ時間 10,697 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 68 ms
76,444 KB
testcase_01 AC 70 ms
76,360 KB
testcase_02 AC 72 ms
76,332 KB
testcase_03 AC 70 ms
76,428 KB
testcase_04 AC 68 ms
76,204 KB
testcase_05 AC 69 ms
76,588 KB
testcase_06 AC 68 ms
76,248 KB
testcase_07 AC 68 ms
76,268 KB
testcase_08 AC 71 ms
76,644 KB
testcase_09 AC 69 ms
76,584 KB
testcase_10 AC 70 ms
76,588 KB
testcase_11 AC 68 ms
76,436 KB
testcase_12 AC 70 ms
76,364 KB
testcase_13 AC 75 ms
76,404 KB
testcase_14 AC 72 ms
76,264 KB
testcase_15 AC 71 ms
76,372 KB
testcase_16 AC 73 ms
76,376 KB
testcase_17 AC 73 ms
76,332 KB
testcase_18 AC 74 ms
76,408 KB
testcase_19 AC 72 ms
76,400 KB
testcase_20 AC 73 ms
76,636 KB
testcase_21 AC 82 ms
79,212 KB
testcase_22 AC 82 ms
78,916 KB
testcase_23 AC 81 ms
79,188 KB
testcase_24 AC 84 ms
79,104 KB
testcase_25 AC 82 ms
79,144 KB
testcase_26 AC 85 ms
79,132 KB
testcase_27 AC 85 ms
79,064 KB
testcase_28 AC 83 ms
79,240 KB
testcase_29 AC 98 ms
79,544 KB
testcase_30 AC 90 ms
79,412 KB
testcase_31 AC 92 ms
79,384 KB
testcase_32 AC 95 ms
79,288 KB
testcase_33 AC 94 ms
79,516 KB
testcase_34 AC 92 ms
79,292 KB
testcase_35 AC 94 ms
79,372 KB
testcase_36 AC 89 ms
79,388 KB
testcase_37 AC 92 ms
79,404 KB
testcase_38 AC 91 ms
79,752 KB
権限があれば一括ダウンロードができます

ソースコード

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