結果

問題 No.1910 High Element on Grid
コンテスト
ユーザー shotoyoo
提出日時 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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 5 WA * 10 RE * 26
権限があれば一括ダウンロードができます

ソースコード

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