結果

問題 No.1910 High Element on Grid
ユーザー shotoyooshotoyoo
提出日時 2022-04-22 22:53:01
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,711 bytes
コンパイル時間 267 ms
コンパイル使用メモリ 82,632 KB
実行使用メモリ 113,200 KB
最終ジャッジ日時 2024-06-24 04:13:06
合計ジャッジ時間 9,729 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 5 WA * 36
権限があれば一括ダウンロードができます

ソースコード

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()
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)
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
for item in ans:
    write(" ".join(map(str, item)))
0