結果

問題 No.3739 Stronger Network
コンテスト
ユーザー 👑 kencho
提出日時 2026-09-11 00:44:08
言語 PyPy3
(7.3.23 + ACL)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 254 ms / 2,000 ms
+ 899µs
コード長 2,015 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 75 ms
コンパイル使用メモリ 81,280 KB
実行使用メモリ 108,392 KB
最終ジャッジ日時 2026-09-19 13:15:57
合計ジャッジ時間 7,612 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge4_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 48
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys

def cyclic_gray(n):
    if n == 2:
        return [0, 1]
    p = 1 << (n.bit_length() - 1)
    if p == n:
        return [i ^ (i >> 1) for i in range(n)]
    r = n - p
    small = cyclic_gray(r)
    u, v = small[0], small[1]
    difference = u ^ v
    changed = (difference & -difference).bit_length() - 1
    base = []
    for i in range(p):
        x = i ^ (i >> 1)
        if (x & 1) != ((x >> changed) & 1):
            x ^= 1 | 1 << changed
        base.append(x ^ u)
    return [u, p + u] + [p + small[i] for i in range(r - 1, 0, -1)] + [v] + base[2:]

def bit_positions(h, w):
    rh, rw = (h - 1).bit_length(), (w - 1).bit_length()
    bh = [(h - 1 >> (rh - 1 - i)) & 1 for i in range(rh)]
    bw = [(w - 1 >> (rw - 1 - j)) & 1 for j in range(rw)]
    inf = 10**30
    dp = [[inf] * (rw + 1) for _ in range(rh + 1)]
    take = [[False] * (rw + 1) for _ in range(rh + 1)]
    dp[rh][rw] = 0
    for i in range(rh, -1, -1):
        for j in range(rw, -1, -1):
            if i == rh and j == rw: continue
            remain = rh - i + rw - j
            if i < rh:
                dp[i][j] = (bh[i] << (remain - 1)) + dp[i + 1][j]
                take[i][j] = True
            if j < rw:
                value = (bw[j] << (remain - 1)) + dp[i][j + 1]
                if value < dp[i][j]: dp[i][j], take[i][j] = value, False
    ph, pw, i, j = [0] * rh, [0] * rw, 0, 0
    for output in range(rh + rw - 1, -1, -1):
        if i < rh and (j == rw or take[i][j]): ph[rh - 1 - i] = output; i += 1
        else: pw[rw - 1 - j] = output; j += 1
    return ph, pw

def deposit(x, positions):
    return sum(1 << positions[b] for b in range(len(positions)) if x >> b & 1)

h, w = map(int, sys.stdin.buffer.read().split())
if h % 2 or w % 2:
    print(-1)
else:
    gh, gw = cyclic_gray(h), cyclic_gray(w)
    ph, pw = bit_positions(h, w)
    rows, cols = [deposit(x, ph) for x in gh], [deposit(x, pw) for x in gw]
    print("\n".join(" ".join(str(rows[r] | cols[c]) for c in range(w)) for r in range(h)))
0