結果
問題 | No.3131 Twin Slide Puzzles |
ユーザー |
👑 |
提出日時 | 2024-12-23 05:47:08 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,411 ms / 4,000 ms |
コード長 | 3,130 bytes |
コンパイル時間 | 201 ms |
コンパイル使用メモリ | 81,912 KB |
実行使用メモリ | 170,736 KB |
最終ジャッジ日時 | 2025-06-20 02:19:57 |
合計ジャッジ時間 | 49,802 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 59 |
ソースコード
from itertools import permutations from random import shuffle N = int(input()) A = [list(map(int, input().split())) for _ in range(N)] class fenwick_tree(): n=1 data=[0 for i in range(n)] def __init__(self,N): self.n=N self.data=[0 for i in range(N)] def add(self,p,x): assert 0<=p<self.n,"0<=p<n,p={0},n={1}".format(p,self.n) p+=1 while(p<=self.n): self.data[p-1]+=x p+=p& -p def sum(self,l,r): assert (0<=l and l<=r and r<=self.n),"0<=l<=r<=n,l={0},r={1},n={2}".format(l,r,self.n) return self.sum0(r)-self.sum0(l) def sum0(self,r): s=0 while(r>0): s+=self.data[r-1] r-=r&-r return s def serialize(X): serialized = [] for row in X: serialized.extend(row) return serialized def calc_parity(X): for i in range(len(X)): for j in range(len(X[i])): if X[i][j] == 0: return (i + j) % 2 def calc_inversion(array): MAX = max(array) bit = fenwick_tree(MAX + 1) result = 0 for a in array: result += bit.sum(0, MAX + 1) - bit.sum(0, a + 1) bit.add(a, 1) return result def is_valid(X): parity = calc_parity(X) serialized = serialize(X) inversion = calc_inversion(serialized) return parity == inversion % 2 def fun(X): result = 0 for i in range(len(X)): for j in range(len(X[i])): result += A[i][j] * X[i][j] return result def random_pick(): array = list(range(N**2)) while True: shuffle(array) yield array[:] val = dict() loop = permutations(range(N**2)) if N <= 3 else random_pick() if N <= 3: for perm in permutations(range(N**2)): X = [[perm[i * N + j] for j in range(N)] for i in range(N)] if not is_valid(X): continue f = fun(X) if f in val and X != val[f]: print("Yes") for row in val[f]: print(*row) for row in X: print(*row) exit() val[f] = X else: perm = list(range(4**2)) while True: shuffle(perm) X = [] for i in range(0, 4**2, N): X.append(perm[i : i + N]) if not is_valid(X): continue f = fun(X) if f in val and X != val[f]: print("Yes") for i in range(N): for j in range(N): if i * N + j < 4**2: print(val[f][i][j], end=" ") else: print(i * N + j, end=" ") print() for i in range(N): for j in range(N): if i * N + j < 4**2: print(X[i][j], end=" ") else: print(i * N + j, end=" ") print() exit() val[f] = X print("No")