結果
問題 |
No.1370 置換門松列
|
ユーザー |
![]() |
提出日時 | 2021-01-30 03:51:27 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 459 ms / 2,000 ms |
コード長 | 1,281 bytes |
コンパイル時間 | 330 ms |
コンパイル使用メモリ | 12,544 KB |
実行使用メモリ | 41,252 KB |
最終ジャッジ日時 | 2024-09-14 19:24:05 |
合計ジャッジ時間 | 5,261 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge6 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 25 |
ソースコード
def kado(x,y,z): if x==z: return 0 if y<x and y<z: return 1 if y>x and y>z: return 1 return 0 N,M=map(int,input().split()) A=list(map(int,input().split())) for i in range(N-2): if A[i]==A[i+2]: print("No") exit() E=[] for i in range(N-1): if i%2==0: E.append((A[i],A[i+1])) else: E.append((A[i+1],A[i])) # Kahnのアルゴリズム EDGEIN=[0]*(M+1) # その点に入るEDGEの個数 EDGEOUTLIST=[[] for i in range(M+1)] # EDGEの行き先 for x,y in E: EDGEIN[y]+=1 EDGEOUTLIST[x].append(y) from collections import deque QUE = deque() for i in range(M+1): if EDGEIN[i]==0: QUE.append(i) # 行き先のない点をQUEに入れる TOP_SORT=[] while QUE: x=QUE.pop() TOP_SORT.append(x) # 行き先がない点を答えに入れる for to in EDGEOUTLIST[x]: EDGEIN[to]-=1 # 行き先がない点を削除し,そこから一歩先の点のEDGEINを一つ減らす. if EDGEIN[to]==0: QUE.appendleft(to) T=[0] for t in TOP_SORT: if t==0: continue T.append(t) TOP_INV=[-1]*(M+1) for i,x in enumerate(T): TOP_INV[x]=i if -1 in TOP_INV: print("No") else: print("Yes") print(*TOP_INV[1:])