結果

問題 No.3740 Troublesome Congestion
コンテスト
ユーザー 👑 kencho
提出日時 2026-08-12 15:04:02
言語 Python3
(3.14.7 + numpy 2.5.2 + scipy 1.18.0 + ACL)
コンパイル:
python3 -mpy_compile _filename_
実行:
python3 _filename_
結果
WA  
実行時間 -
コード長 3,239 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 59 ms
コンパイル使用メモリ 15,744 KB
実行使用メモリ 12,160 KB
最終ジャッジ日時 2026-09-19 12:38:40
合計ジャッジ時間 9,433 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
サブタスク 配点 結果
部分点1 20 % AC * 2 WA * 5
部分点2 30 % AC * 2 WA * 10
満点 50 % AC * 2 WA * 24
合計 4 * 0% = 0 点
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys

N = 40


def put(a, r, c):
    if 0 <= r < N and 0 <= c < N and a[r][c] != "P":
        a[r][c] = "."


def paths(a):
    zero = [[0] * N for _ in range(N)]
    one = [[0] * N for _ in range(N)]
    for r in range(N):
        for c in range(N):
            if a[r][c] == "#":
                continue
            if r == c == 0:
                zero[r][c] = 1
                continue
            z = (zero[r - 1][c] if r else 0) + (zero[r][c - 1] if c else 0)
            o = (one[r - 1][c] if r else 0) + (one[r][c - 1] if c else 0)
            if a[r][c] == "P":
                one[r][c] = z
            else:
                zero[r][c], one[r][c] = z, o
    return one[-1][-1]


def connect(a, cells, upper):
    if not cells:
        return
    cells.sort()
    r, c = cells[0]
    for nr, nc in cells[1:]:
        if upper:
            for x in range(c, nc + 1): put(a, r, x)
            for y in range(r, nr + 1): put(a, y, nc)
        else:
            for y in range(r, nr + 1): put(a, y, c)
            for x in range(c, nc + 1): put(a, nr, x)
        r, c = nr, nc
    if upper:
        for x in range(c, N): put(a, r, x)
        for y in range(r, N): put(a, y, N - 1)
    else:
        for y in range(r, N): put(a, y, c)
        for x in range(c, N): put(a, N - 1, x)


def build(m):
    a = [["#"] * N for _ in range(N)]
    switches, upper, lower = [], [], []
    r = c = stage = 0
    while True:
        if stage % 2 == 0:
            if r + 4 >= N - 1 or c + 4 >= N - 1:
                break
            for y in range(r, r + 3):
                for x in range(c, c + 2): put(a, y, x)
            switches += [(r, c + 2), (r + 1, c + 2)]
            upper += [(r, c + 3), (r + 1, c + 3)]
            for cell in upper[-2:]: put(a, *cell)
            put(a, r + 3, c + 1)
            put(a, r + 3, c + 2)
            r, c = r + 3, c + 2
        else:
            if r + 4 >= N - 1 or c + 4 >= N - 1:
                break
            for y in range(r, r + 2):
                for x in range(c, c + 3): put(a, y, x)
            switches += [(r + 2, c), (r + 2, c + 1)]
            lower += [(r + 3, c), (r + 3, c + 1)]
            for cell in lower[-2:]: put(a, *cell)
            put(a, r + 1, c + 3)
            put(a, r + 2, c + 3)
            r, c = r + 2, c + 3
        stage += 1
    connect(a, upper, True)
    connect(a, lower, False)

    values = []
    for r, c in switches:
        b = [row[:] for row in a]
        b[r][c] = "P"
        values.append(paths(b))
    chosen = []
    for i in sorted(range(len(values)), key=lambda i: values[i], reverse=True):
        if 0 < values[i] <= m:
            m -= values[i]
            chosen.append(i)
    if m:
        return None
    for i in chosen:
        r, c = switches[i]
        a[r][c] = "P"

    a = [list(reversed(row)) for row in reversed(a)]
    for r in range(N):
        for c in range(N):
            if a[r][c] == "P":
                a[r][c] = "."
    a[0][0] = a[-1][-1] = "."
    a[0][1] = a[1][0] = "P"
    return a


data = list(map(int, sys.stdin.buffer.read().split()))
answer = []
for m in data[1:]:
    grid = build(m)
    answer += ["-1"] if grid is None else [str(N)] + ["".join(row) for row in grid]
print("\n".join(answer))
0