結果

問題 No.3131 Twin Slide Puzzles
コンテスト
ユーザー 👑 SPD_9X2
提出日時 2025-04-25 23:41:34
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 637 ms / 4,000 ms
コード長 1,710 bytes
コンパイル時間 338 ms
コンパイル使用メモリ 81,716 KB
実行使用メモリ 142,672 KB
最終ジャッジ日時 2025-06-20 02:48:47
合計ジャッジ時間 28,132 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 59
権限があれば一括ダウンロードができます

ソースコード

diff # 

"""

https://yukicoder.me/problems/no/3131


互換の回数の偶奇を見ればいい

同じものの構築は…
適当に作るとヒットするのでは？

"""

import sys
import random

def printans(P):

    ans = [[None] * N for i in range(N)]
    for X in range(N*N):
        xi,xj = X//N,X%N
        ans[xi][xj] = P[X]

    for i in range(N):
        print (*ans[i])

N = int(input())

A = [ list(map(int,input().split())) for i in range(N) ]

P = [i for i in range(N*N)]

dic = {}
S = 0
S2 = 0

mod = random.randint(10**17,10**18)
mod2= random.randint(10**17,10**18)

for i in range(N):
    for j in range(N):
        S += A[i][j] * P[i*N+j]
dic[S] = (0,S2)

move = []

zero = 0

for loop in range(1,5*(10**5)):

    X = random.randint(0,min(N*N-1,20))
    Y = random.randint(0,min(N*N-2,20))
    if X == Y:
        Y += 1

    xi,xj = X//N,X%N
    yi,yj = Y//N,Y%N

    S2 -= (P[X]*A[xi][xj])**2 + (P[Y]*A[yi][yj])**2
    S2 %= mod2
    S -= P[X]*A[xi][xj] + P[Y]*A[yi][yj]
    S %= mod
    
    P[X],P[Y] = P[Y],P[X]
    S += P[X]*A[xi][xj] + P[Y]*A[yi][yj]
    S2 += (P[X]*A[xi][xj])**2 + (P[Y]*A[yi][yj])**2
    S2 %= mod2
    S %= mod

    move.append( (X,Y) )

    if P[X] == 0:
        zero = (xi+xj)%2
    if P[Y] == 0:
        zero = (yi+yj)%2


    # print (P,S,loop%2,zero)

    if loop % 2 == zero:
        if S in dic:
            if dic[S][1] == S2:
                pass
            else:
                print ("Yes")
                ansA = printans(P)
                while len(move) > dic[S][0]:
                    x,y = move.pop()
                    P[x],P[y] = P[y],P[x]
                ansB = printans(P)
                sys.exit()

        dic[S] = (loop,S2)

print ("No")
0