結果

問題 No.1370 置換門松列
ユーザー chineristAC
提出日時 2021-01-29 21:32:35
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 164 ms / 2,000 ms
コード長 1,279 bytes
コンパイル時間 920 ms
コンパイル使用メモリ 82,144 KB
実行使用メモリ 105,364 KB
最終ジャッジ日時 2024-09-14 19:18:50
合計ジャッジ時間 3,907 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque

N,M = map(int,input().split())
a = list(map(int,input().split()))
a = [a[i]-1 for i in range(N)]

for i in range(N-2):
    if a[i]==a[i+1] or a[i]==a[i+2] or a[i+1]==a[i+2]:
        exit(print("No"))

edge = [[] for i in range(M)]
deg = [0 for i in range(M)]
for i in range(N-1):
    u,v = a[i],a[i+1]
    if i%2==0:
        edge[v].append(u)
        deg[u] += 1
    else:
        edge[u].append(v)
        deg[v] += 1

deq = deque([v for v in range(M) if deg[v]==0])
X = [-1 for i in range(M)]
val = 1
while deq:
    v = deq.popleft()
    X[v] = val
    val += 1
    for nv in edge[v]:
        deg[nv] -= 1
        if deg[nv]==0:
            deq.append(nv)

if -1 not in X:
    print("Yes")
    print(*X)
    exit()

edge = [[] for i in range(M)]
deg = [0 for i in range(M)]
for i in range(N-1):
    u,v = a[i],a[i+1]
    if i%2==1:
        edge[v].append(u)
        deg[u] += 1
    else:
        edge[u].append(v)
        deg[v] += 1

deq = deque([v for v in range(M) if deg[v]==0])
X = [-1 for i in range(M)]
val = 1
while deq:
    v = deq.popleft()
    X[v] = val
    val += 1
    for nv in edge[v]:
        deg[nv] -= 1
        if deg[nv]==0:
            deq.append(nv)


if -1 not in X:
    print("Yes")
    print(*X)
    exit()

print("No")
0