No.2803 Bocching Star
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 152
作問者 :
hirayuu_yc
/ テスター :
highlighter
Magentor
keisuke6
silv723
Yoyoyo8128
zeta7532
fact493
タグ : / 解いたユーザー数 152
作問者 :
![highlighter](https://pbs.twimg.com/profile_images/1707374069132439552/b_BWx6c8.png)
![Magentor](https://pbs.twimg.com/profile_images/1715389554197495808/7HlNzj_p.jpg)
![keisuke6](https://pbs.twimg.com/profile_images/1675785204974354432/k3Bvkvyj.jpg)
![fact493](https://pbs.twimg.com/profile_images/1641449306531192836/GjfyenV1.jpg)
問題文最終更新日: 2024-07-12 20:52:07
問題文
夜空に $N$ 個の星があります。星には $1,2,\dots,N$ と番号がついています。
夜空は数直線とみなすことができ、星 $i$ は座標 $P_i$ にあります。同じ座標に複数の星がある場合もあります。
各星は、距離 $S$ 以内に別の星がないとき、またその時に限り孤立した星といいます。
より厳密には、星 $i$ が孤立した星であることは、$i\ne j$ なる任意の $j$ について $S<|P_i-P_j|$ であることと同値です。
孤立した星を番号の昇順に列挙してください。
入力
$N\ S$ $P_1\ P_2\dots P_N$
- $1\leq N\leq 2\times 10^5$
- $0\leq S\leq 10^9$
- $0\leq P_i\leq 10^9$
- 孤立した星は $1$ つ以上存在する
- 入力はすべて整数
出力
$2$ 行出力してください。
$1$ 行目には、孤立した星の個数を出力してください。
$2$ 行目には、孤立した星の番号を昇順に並べたものを半角スペースで区切って出力してください。
最後に改行してください。
サンプル
サンプル1
入力
4 2 3 1 6 10
出力
2 3 4
星 $1$ と星 $2$ は距離 $2$ です。そのため、星 $1$ と星 $2$ は孤立した星ではありません。
星 $1,2,3$ と星 $4$ の距離はそれぞれ $7,9,4$ なので、星 $4$ は孤立した星です。同様に、星 $3$ も孤立した星であることが確認できます。
たとえば、$2$ 行目に 4 3
と出力することは許されません。番号が昇順に並んでいないためです。
サンプル2
入力
1 1000000000 0
出力
1 1
夜空には星 $1$ 以外に星はないようです。
サンプル3
入力
9 0 9 9 8 2 4 4 3 5 3
出力
3 3 4 8
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。