No.2803 Bocching Star
タグ : / 解いたユーザー数 168
作問者 :
hirayuu_yc
/ テスター :
highlighter
Magentor
keisuke6
silv723
Yoyoyo8128
zeta7532
fact493
Story
You do not necessarily have to read this section.
halc: "The Paken training camp sure was fun."
QgQ: "But you couldn't form a team at all."
halc: "Shut up, you loophole team."
Problem Statement
There are $N$ stars in the night sky. The stars are numbered $1,2,\dots,N$.
The night sky can be regarded as a number line, and star $i$ is at coordinate $P_i$. Multiple stars may be at the same coordinate.
A star is called an isolated star if and only if there is no other star within distance $S$ of it.
More strictly, star $i$ being an isolated star is equivalent to $S<|P_i-P_j|$ holding for every $j$ such that $i\ne j$.
List the isolated stars in ascending order of their numbers.
Input
$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$
- There is at least $1$ isolated star.
- All input values are integers.
Output
Output $2$ lines.
On the $1$st line, output the number of isolated stars.
On the $2$nd line, output the numbers of the isolated stars in ascending order, separated by single-byte spaces.
Print a newline at the end.
Sample
Sample 1
Input
4 2 3 1 6 10
Output
2 3 4
Star $1$ and star $2$ are at distance $2$. Therefore, star $1$ and star $2$ are not isolated stars.
The distances between stars $1,2,3$ and star $4$ are $7,9,4$ respectively, so star $4$ is an isolated star. Similarly, it can be verified that star $3$ is also an isolated star.
For example, outputting 4 3 on the $2$nd line is not allowed, because the numbers are not in ascending order.
Sample 2
Input
1 1000000000 0
Output
1 1
It seems there are no stars in the night sky other than star $1$.
Sample 3
Input
9 0 9 9 8 2 4 4 3 5 3
Output
3 3 4 8
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。