結果

問題 No.1910 High Element on Grid
ユーザー shotoyooshotoyoo
提出日時 2022-04-22 22:54:18
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,994 bytes
コンパイル時間 209 ms
コンパイル使用メモリ 82,552 KB
実行使用メモリ 111,248 KB
最終ジャッジ日時 2024-06-24 04:14:26
合計ジャッジ時間 8,761 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 48 ms
56,828 KB
testcase_01 WA -
testcase_02 WA -
testcase_03 AC 45 ms
56,472 KB
testcase_04 RE -
testcase_05 WA -
testcase_06 RE -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 RE -
testcase_11 WA -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
testcase_22 RE -
testcase_23 RE -
testcase_24 RE -
testcase_25 RE -
testcase_26 RE -
testcase_27 RE -
testcase_28 RE -
testcase_29 RE -
testcase_30 RE -
testcase_31 AC 46 ms
56,920 KB
testcase_32 RE -
testcase_33 RE -
testcase_34 RE -
testcase_35 RE -
testcase_36 AC 61 ms
67,864 KB
testcase_37 AC 113 ms
95,732 KB
testcase_38 AC 89 ms
81,568 KB
testcase_39 WA -
testcase_40 WA -
testcase_41 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys, random
input = lambda : sys.stdin.readline().rstrip()

write = lambda x: sys.stdout.write(x+"\n"); writef = lambda x: print("{:.12f}".format(x))
debug = lambda x: sys.stderr.write(x+"\n")
YES="Yes"; NO="No"; pans = lambda v: print(YES if v else NO); inf=10**18
LI = lambda : list(map(int, input().split()))
def dlist(*l, fill=0):
    if len(l)==1:
        return [fill]*l[0]
    ll = l[1:]
    return [dlist(*ll, fill=fill) for _ in range(l[0])]
sys.setrecursionlimit(3*10**5+10)

def cycle(rns, ds):
    """出次数0の頂点を削除しつづける
    DAGならTPS順序も求まる
    rns: 逆辺の隣接リスト
    ds: もとのグラフにおける出次数
    返り値
    vs: 除かれた頂点
    done: 除いたフラグ
    doneがすべて1でない場合、サイクルが存在する (サイクルに到達できる頂点のみdone==0となる)
    """
    from collections import deque
    q = deque()
    n = len(rns)
    done = [False] * n
    for u in range(n):
        if ds[u]==0:
            q.append(u)
            done[u] = True
    vs = []
    while q:
        u = q.popleft()
        vs.append(u)
        for v in rns[u]:
            if done[v]:
                # これがないとdsが不当に減ってバグになる
                continue
            ds[v] -= 1
            if ds[v]==0:
                done[v] = True
                q.append(v)
    return vs,done

h,w = list(map(int, input().split()))
rs = LI()
cs = LI()
def main(h,w,rs,cs):
    vs = [[0]*w for _ in range(h)]
    for i in range(h):
        vs[i][rs[i]-1] = 1
    for i in range(w):
        vs[cs[i]-1][i] = 1
    N = h*w
    # ns = [[] for _ in range(N)]
    rns = [[] for _ in range(N)]
    ds = [0]*N
    for i in range(h):
        v = rs[i]-1
        uu = w*i + v
        for j in range(v):
            if vs[i][j]:
                vv = w*i + j
    #             ns[vv].append(uu)
                rns[uu].append(vv)
                ds[vv] += 1
        for j in range(v+1,w):
            if vs[i][j]:
                vv = w*i + j
    #             ns[vv].append(uu)
                rns[uu].append(vv)
                ds[vv] += 1
    for j in range(w):
        v = cs[j]-1
        uu = w*v + j
        for i in range(v):
            if vs[i][j]:
                vv = w*i + j
    #             ns[vv].append(uu)
                rns[uu].append(vv)
                ds[vv] += 1
        for i in range(v+1,h):
            if vs[i][j]:
                vv = w*i + j
    #             ns[vv].append(uu)
                rns[uu].append(vv)
                ds[vv] += 1
    vals, done = cycle(rns, ds)
    assert all(done)
    ans = [[0]*w for _ in range(h)]
    val = 10**9
    for i in range(h):
        for j in range(w):
            ans[i][j] = (1+i+j)
    for ind in vals:
        i,j = divmod(ind, w)
        if vs[i][j]==0:
            continue
        ans[i][j] = val
        val -= 1
    return ans
ans = main(h,w,rs,cs)
for item in ans:
    write(" ".join(map(str, item)))
0