結果

問題 No.3335 ReCT
コンテスト
ユーザー ikatakos
提出日時 2025-11-07 22:25:56
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 142 ms / 2,000 ms
コード長 4,949 bytes
コンパイル時間 85 ms
コンパイル使用メモリ 13,312 KB
実行使用メモリ 25,088 KB
最終ジャッジ日時 2025-11-07 22:26:12
合計ジャッジ時間 9,799 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 97
権限があれば一括ダウンロードができます

ソースコード

diff # 

def last_swap(ans, is_swapped):
    if is_swapped:
        ans = list(zip(*ans))
    return ans


def solve_c(h, w):
    is_swapped = h > w
    if is_swapped:
        h, w = w, h

    # h <= w

    ans = [[0] * w for _ in range(h)]

    if h == 2:
        return 0, None
    if h == 3:
        if w % 2 != 0:
            return 0, None
        if w % 4 == 0:
            t = w // 4
            for b in range(t):
                x = b * 2 + 1
                y = b * 2 + 2
                ans[0][b * 4:(b + 1) * 4] = [x, x, x, y]
                ans[1][b * 4:(b + 1) * 4] = [x, y, x, y]
                ans[2][b * 4:(b + 1) * 4] = [x, y, y, y]
            k = t * 2
        else:
            t = (w - 6) // 4
            for b in range(t):
                x = b * 2 + 1
                y = b * 2 + 2
                ans[0][b * 4:(b + 1) * 4] = [x, x, x, y]
                ans[1][b * 4:(b + 1) * 4] = [x, y, x, y]
                ans[2][b * 4:(b + 1) * 4] = [x, y, y, y]
            x = t * 2 + 1
            y = t * 2 + 2
            z = t * 2 + 3
            ans[0][t * 4:t * 4 + 6] = [x, x, x, y, y, y]
            ans[1][t * 4:t * 4 + 6] = [x, z, x, y, z, y]
            ans[2][t * 4:t * 4 + 6] = [x, z, z, z, z, y]
            k = z
        return k, last_swap(ans, is_swapped)

    if h % 2 == 0:
        wrap = (h - 4) // 2
        ans[wrap + 0][:w - wrap] = [1] * (w - wrap)
        ans[wrap + 1][:w - wrap] = [1] + [2] * (w - wrap - 1)
        ans[wrap + 2][:w - wrap] = [1] * (w - wrap - 1) + [2]
        ans[wrap + 3][:w - wrap] = [2] * (w - wrap)
        for i in range(wrap):
            ans[i][:w - i] = [3 + i] * (w - i)
            ans[h - i - 1][:w - i] = [3 + i] * (w - i)
            for j in range(i, h - i):
                ans[j][w - i - 1] = 3 + i
        return wrap + 2, last_swap(ans, is_swapped)

    k, ans2 = solve_c(h - 1, w - 1)
    for i in range(h - 1):
        ans[i][:-1] = ans2[i]
        ans[i][-1] = k + 1
    ans[-2][0] = k + 1
    ans[-1] = [k + 1] * w
    return k + 1, last_swap(ans, is_swapped)


def solve_t(h, w):
    is_swapped = h > w
    if is_swapped:
        h, w = w, h

    # h <= w
    ans = [[0] * w for _ in range(h)]
    if h == 2:
        return 0, None
    if h == 3:
        if w < 6:
            return 0, None
        ans[0][:4] = [1, 2, 2, 2]
        ans[1][:4] = [1, 1, 2, 3]
        ans[2][:4] = [1, 3, 3, 3]
        ans[0][4:w - 1] = [2] * (w - 5)
        ans[1][4:w - 1] = [4] * (w - 5)
        ans[2][4:w - 1] = [3] * (w - 5)
        ans[0][-1] = ans[1][-1] = ans[2][-1] = 4
        return 4, last_swap(ans, is_swapped)
    if h == 4:
        ans[0] = [1] * (w - 1) + [4]
        ans[1] = [2, 1] + [4] * (w - 2)
        ans[2] = [2] * (w - 2) + [3, 4]
        ans[3] = [2] + [3] * (w - 1)
        return 4, last_swap(ans, is_swapped)
    if h == 5 and w <= 7:
        if w == 5:
            k = 5
            ans[0] = [1, 2, 2, 2, 2]
            ans[1] = [1, 1, 4, 2, 5]
            ans[2] = [1, 3, 4, 4, 5]
            ans[3] = [1, 3, 4, 5, 5]
            ans[4] = [3, 3, 3, 3, 5]
        elif w == 6:
            k = 6
            ans[0] = [1, 2, 2, 2, 2, 6]
            ans[1] = [1, 1, 4, 2, 6, 6]
            ans[2] = [1, 3, 4, 4, 5, 6]
            ans[3] = [1, 3, 4, 5, 5, 6]
            ans[4] = [3, 3, 3, 3, 5, 6]
        else:
            k = 7
            ans[0] = [1, 2, 2, 2, 2, 2, 2]
            ans[1] = [1, 1, 2, 4, 6, 6, 6]
            ans[2] = [1, 3, 2, 4, 4, 6, 7]
            ans[3] = [1, 3, 2, 4, 5, 7, 7]
            ans[4] = [3, 3, 3, 5, 5, 5, 7]
        return k, last_swap(ans, is_swapped)
    k, ans2 = solve_t(h - 2, w - 2)
    x = k + 1
    y = k + 2
    z = k + 3
    ans[0] = [y] * w
    ans[1] = [x, y] + ans2[0]
    ans[2] = [x, x] + ans2[1]
    for i in range(3, h - 1):
        ans[i] = [x, z] + ans2[i - 1]
    ans[h - 1] = [z] * w
    return z, last_swap(ans, is_swapped)


def solve_ct(h, w):
    is_swapped = h > w
    if is_swapped:
        h, w = w, h

    ans = [[0] * w for _ in range(h)]
    if h == 2:
        return 0, None
    if h == 3:
        ans[0] = [1] * (w - 1) + [2]
        ans[1] = [1] + [2] * (w - 1)
        ans[2] = [1] * (w - 1) + [2]
        return 2, last_swap(ans, is_swapped)
    if h == 4:
        ans[0] = [1] + [3] * (w - 1)
        ans[1] = [1] * (w - 1) + [3]
        ans[2] = [1, 2] + [3] * (w - 2)
        ans[3] = [2] * w
        return 3, last_swap(ans, is_swapped)
    k, ans2 = solve_ct(h - 2, w - 1)
    ans[0] = [k + 1] * w
    for i in range(1, h - 1):
        ans[i] = [k + 1] + ans2[i - 1]
    ans[h - 1] = [k + 1] * w
    return k + 1, last_swap(ans, is_swapped)


def solve(h, w):
    def sub(solve_func, h, w):
        k, ans = solve_func(h, w)
        if k == 0:
            print(-1)
        else:
            print(k)
            for row in ans:
                print(*row)

    sub(solve_c, h, w)
    sub(solve_t, h, w)
    sub(solve_ct, h, w)


h, w = list(map(int, input().split()))
solve(h, w)
0