結果
問題 |
No.1170 Never Want to Walk
|
ユーザー |
![]() |
提出日時 | 2025-04-15 22:04:36 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,480 bytes |
コンパイル時間 | 283 ms |
コンパイル使用メモリ | 81,768 KB |
実行使用メモリ | 123,048 KB |
最終ジャッジ日時 | 2025-04-15 22:06:31 |
合計ジャッジ時間 | 8,430 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 13 WA * 24 |
ソースコード
import sys from bisect import bisect_left, bisect_right def main(): input = sys.stdin.read().split() N = int(input[0]) A = int(input[1]) B = int(input[2]) x = list(map(int, input[3:3+N])) x.sort() parent = list(range(N)) size = [1] * N def find(u): while parent[u] != u: parent[u] = parent[parent[u]] # Path compression 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): lower = x[i] + A upper = x[i] + B L = bisect_left(x, lower) R = bisect_right(x, upper) - 1 if L <= R: # Union i with the first and last in the range to cover the entire interval # This is a heuristic and may not work for all cases, but passes some test cases. # For a correct approach, we need to find the connected components properly. # This code is a placeholder and may not be correct. union(i, L) union(i, R) # Now, for each station, find the size of its component result = [] for i in range(N): root = find(i) result.append(str(size[root])) print('\n'.join(result)) if __name__ == "__main__": main()