結果
問題 |
No.1170 Never Want to Walk
|
ユーザー |
![]() |
提出日時 | 2025-04-15 21:59:03 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,089 bytes |
コンパイル時間 | 416 ms |
コンパイル使用メモリ | 82,512 KB |
実行使用メモリ | 123,616 KB |
最終ジャッジ日時 | 2025-04-15 22:00:10 |
合計ジャッジ時間 | 8,046 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 13 WA * 24 |
ソースコード
import bisect def main(): import sys input = sys.stdin.read data = input().split() N = int(data[0]) A = int(data[1]) B = int(data[2]) x = list(map(int, data[3:3+N])) parent = list(range(N)) size = [1] * N def find(u): while parent[u] != u: parent[u] = parent[parent[u]] u = parent[u] return u def union(u, v): u_root = find(u) v_root = find(v) if u_root == v_root: return if size[u_root] < size[v_root]: u_root, v_root = v_root, u_root parent[v_root] = u_root size[u_root] += size[v_root] for i in range(N): xi = x[i] low = xi + A high = xi + B j = bisect.bisect_left(x, low) if j >= N or x[j] > high: continue k = bisect.bisect_right(x, high) - 1 if j <= k: union(i, j) union(i, k) result = [size[find(i)] for i in range(N)] print('\n'.join(map(str, result))) if __name__ == "__main__": main()