結果

問題 No.3131 Twin Slide Puzzles
ユーザー lif4635
提出日時 2025-04-25 10:22:33
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,083 ms / 4,000 ms
コード長 2,500 bytes
コンパイル時間 244 ms
コンパイル使用メモリ 82,264 KB
実行使用メモリ 138,816 KB
最終ジャッジ日時 2025-06-20 02:38:01
合計ジャッジ時間 45,430 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 59
権限があれば一括ダウンロードができます

ソースコード

diff # 

class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
    
    def build(self, arr):
        for i,a in enumerate(arr):
            self.data[i+1] = a
        for i in range(1, self.n+1):
            if i + (i&-i) <= self.n:
                self.data[i + (i&-i)] += self.data[i]
    
    def add(self, p, x):
        p += 1
        while p <= self.n:
            self.data[p] += x
            p += p& -p
    
    def sum0(self, r):
        s = 0
        while r:
            s += self.data[r]
            r -= r& -r
        return s
    
    def sum(self, l, r):
        s = 0
        while r:
            s += self.data[r]
            r -= r& -r
        while l:
            s -= self.data[l]
            l -= l& -l
        return s
    
    def get(self, p):
        return self.sum0(p+1) - self.sum0(p)
    
    def __str__(self):
        return str([self.get(i) for i in range(self.n)])

def inversion_cnt(lst:list) -> int:
    """
    i > j && a_i < a_j
    """
    n = len(lst)
    ft = BIT(n+10)
    ans = [0]*n
    for i in range(n):
        ans[i] = ft.sum(lst[i],n+10)
        ft.add(lst[i], 1)
    return ans

def valid(n, p):
    s = sum(inversion_cnt(p))
    if 0 in p:
        ij = p.index(0)
        i, j = divmod(ij, n)
        return s % 2 == (i + j) % 2
    else:
        return s % 2 == 0

def score(p):
    s = sum(a[i] * p[i] for i in range(len(p)))
    return s 

def answer(n, p, q):
    # 答えを出力
    print("Yes")
    l = len(p)
    p = list(p) + [i for i in range(l, n * n)]
    q = list(q) + [i for i in range(l, n * n)]
    assert score(p) == score(q)
    for i in range(n):
        print(*p[i*n:i*n+n])
    for i in range(n):
        print(*q[i*n:i*n+n])
    exit()

n = int(input())
assert 2 <= n <= 500

a = []
for i in range(n):
    ai = [int(x) for x in input().split()]
    a.extend(ai)
    for aij in ai:
        assert 1 <= aij <= 10 ** 8

from itertools import permutations
from random import shuffle

if n <= 3:
    cnt = dict()
    for p in permutations(range(n * n)):
        if valid(n, p):
            s = sum(a[i] * p[i] for i in range(n * n))
            if s in cnt:
                answer(n, p, cnt[s])
            else:
                cnt[s] = p
    print("No")
    exit()

c = 16
p = [i for i in range(c)]

cnt = dict()
while True:
    shuffle(p)
    if valid(n, p):
        s = sum(a[i] * p[i] for i in range(c))
        if s in cnt:
            answer(n, p, cnt[s])
        else:
            cnt[s] = tuple(p)
0