結果

問題 No.2958 Placing Many L-s
ユーザー navel_tos
提出日時 2025-01-11 20:14:10
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 242 ms / 2,000 ms
コード長 4,663 bytes
コンパイル時間 530 ms
コンパイル使用メモリ 81,920 KB
実行使用メモリ 80,384 KB
最終ジャッジ日時 2025-01-11 20:14:21
合計ジャッジ時間 9,413 ms
ジャッジサーバーID
(参考情報)
judge2 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 29
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#yukicoder2958 Placing Many L-s
#
def brute(H, W):
def make_valid():
block = []
for G in ([[1, 1, 1], [x, 0, x ^ 1], [0, 0, 0]] for x in range(2)):
for _ in range(4):
G = [[G[h][~ w] for h in range(3)] for w in range(3)]
for i, (h, w) in enumerate([(h, w) for h in range(3) for w in range(3)]):
if G[h][w] == 1:
break
H = []
for x in range(3):
for y in range(3):
if G[x][y] == 1:
H.append((x - h, y - w))
block.append(H)
return block
block = make_valid()
#DFS (h, w)block[t]
G = [[0] * W for _ in range(H)]
stack = [(0, 0, t) for t in range(8)]
d = 0 #
while stack:
h, w, t = stack.pop()
if h >= 0: #
#1. continue
if not all( (x := h + p) in range(H) and (y := w + q) in range(W) and
G[x][y] == 0 for p, q in block[t] ):
continue
d += 1
stack.append((~ h, w, t))
for p, q in block[t]:
assert G[ x := h + p ][ y := w + q ] == 0
G[x][y] = d
#2.
a = h * W + w
for a in range(a + 1, H * W + 1):
if a == H * W:
break
x, y = a // W, a % W
if G[x][y] == 0:
break
if a == H * W: #
assert all( G[h][w] > 0 for h in range(H) for w in range(W) ), str(G)
return G
x, y = a // W, a % W
for u in range(8):
stack.append((x, y, u))
else: #
h = ~ h
#1.
for p, q in block[t]:
assert G[ x := h + p ][ y := w + q ] == d
G[x][y] = 0
d -= 1
else: #
return G
#H, WH
#H ≡ 0 mod 8: W >= 2(8, 2), (8, 3)
#H ≡ 4 mod 8: W(4, 2)
#H ≡ 2, 6 mod 8: W4(W, H)90
# (4, 2), (8, 2), (8, 3)使
tiles = [[None] * 9 for _ in range(9)]
for h, w in [(4, 2), (8, 2), (8, 3)]:
tiles[h][w] = brute(h, w)
def rotate(G):
if len(G) == 0:
return []
else:
return [[G[h][~ w] for h in range( len(G) )] for w in range( len(G[0]) )]
def solve(H, W):
if H & 1 == W & 1 == 1:
return []
if H & 1:
return rotate( solve(W, H) )
#1. H ≡ 0 mod 8
if H % 8 == 0:
if W == 1:
return []
G = [[0] * W for _ in range(H)]
offset = 0 #
for h in range(0, H, 8):
if W & 1: #(8, 3)
base = tiles[8][3]
for x in range(8):
for y in range(3):
G[h + x][0 + y] = base[x][y] + offset
offset += 6
for w in range( (3 if W & 1 else 0), W - 1, 2 ):
base = tiles[8][2]
for x in range(8):
for y in range(2):
G[h + x][w + y] = base[x][y] + offset
offset += 4
return G
#2. H ≡ 4 mod 8
if H % 8 == 4:
if W & 1 == 1:
return []
G = [[0] * W for _ in range(H)]
offset = 0
base = tiles[4][2]
for h in range(0, H, 4):
for w in range(0, W, 2):
for x in range(4):
for y in range(2):
G[h + x][w + y] = base[x][y] + offset
offset += 2
return G
#3. H ≡ 2, 6 mod 8
if H % 8 in [2, 6]:
return rotate( solve(W, H) ) if W % 4 == 0 else []
return []
#
for _ in range( T := int(input()) ):
H, W = map(int, input().split())
G = solve(H, W)
if G == []:
print(-1)
else:
print(H * W // 4)
for h in range(H):
print(*G[h])
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0