結果
問題 |
No.1170 Never Want to Walk
|
ユーザー |
|
提出日時 | 2024-12-30 18:49:10 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 900 bytes |
コンパイル時間 | 2,458 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 187,788 KB |
最終ジャッジ日時 | 2024-12-30 18:49:41 |
合計ジャッジ時間 | 27,859 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 WA * 1 |
other | AC * 6 WA * 24 TLE * 7 |
ソースコード
import bisect from collections import deque N,A,B=map(int,input().split()) x=list(map(int,input().split())) x.sort() ne=[-1]*N def root(N): if ne[N]<0: return N else: ne[N]=root(ne[N]) return ne[N] def merge(x,y): x,y=root(x),root(y) if ne[x]>ne[y]: x,y=y,x ne[x]+=ne[y] ne[y]=x def same(x,y): return root(x)==root(y) q=deque() stp=set() for i in range(N): if i in stp: continue eru=bisect.bisect_left(x,x[i]+A) aru=bisect.bisect_right(x,x[i]+B) for v in range(eru,aru): if same(i,v) or v in stp: continue stp.add(v) merge(i,v) q.append(v) while q: n=q.popleft() eru=bisect.bisect_left(x,x[n]+A) aru=bisect.bisect_right(x,x[n]+B) for v in range(eru,aru): if same(n,v) or v in stp: continue stp.add(v) merge(n,v) q.append(v) for i in range(N): print(-ne[root(i)])