AT_abc477_b.Standing Outliers

入门

通过率:0%

时间限制:2.00s

内存限制:1024MB

AC君温馨提醒

该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

There are NN people on a number line. The people are numbered 11 to NN, and person ii is at coordinate XiX_i. Multiple people may be at the same coordinate.

A person is said to "stand apart" if their distance to every other person is at least DD.

Formally, person ii is said to "stand apart" if ∣Xi−Xj∣≥D|X_i-X_j| \geq D holds for all j (1≤j≤N, j≠i)j ~ (1 \leq j \leq N,\ j \neq i).

Output the numbers of all people who "stand apart" in ascending order.

数轴上有 NN 个人。这些人编号为 11 到 NN,其中第 ii 个人位于坐标 XiX_i 处。多个人可能位于同一坐标。

若某个人到其余所有人的距离均不小于 DD,则称该人“独立站立”。

形式化地,当对所有 jj(满足 1≤j≤N1 \leq j \leq N 且 j≠ij \neq i)均有 ∣Xi−Xj∣≥D|X_i-X_j| \geq D 成立时,称第 ii 个人“独立站立”。

请按升序输出所有“独立站立”之人的编号。

输入格式

The input is given from Standard Input in the following format:

NN DD
X1X_1 X2X_2 …\dots XNX_N

输入从标准输入中按以下格式给出:

NN DD
X1X_1 X2X_2 …\dots XNX_N

输出格式

Let KK be the number of people who stand apart, and let (P1,P2,…,PK)(P_1,P_2,\dots,P_K) be the sequence of their numbers sorted in ascending order. Output them in the following format:

KK
P1P_1 P2P_2 …\dots PKP_K

If K=0K=0, the second line should be empty.

设 KK 为独自站立的人数,(P1,P2,…,PK)(P_1,P_2,\dots,P_K) 为其编号按升序排列后的序列。请按以下格式输出:

KK
P1P_1 P2P_2 …\dots PKP_K

若 K=0K=0,则第二行应为空。

输入输出样例

  • 输入#1

    3 3
    1 5 7

    输出#1

    1
    1
  • 输入#2

    3 2
    1 1 1

    输出#2

    0
  • 输入#3

    8 3
    4 77 20 26 9 26 22 40

    输出#3

    4
    1 2 5 8

说明/提示

Sample 1 Explanation:
Person 11 has distance 44 to person 22 and distance 66 to person 33, so their distance to every other person is at least DD. Thus, person 11 "stands apart".
Person 22 has distance 22 to person 33, so person 22 does not "stand apart".
Similarly, person 33 has distance 22 to person 22, so person 33 does not "stand apart" either.

Thus, only person 11 "stands apart".

Sample 2 Explanation:
There may be people at the same coordinate. Also, if no one "stands apart", the second line should be empty.

Sample 3 Explanation:
Output the numbers of the people who "stand apart" in ascending order.

Constraints

  • 2≤N≤1002 \le N \le 100
  • 1≤D≤1091 \le D \le 10^9
  • 1≤Xi≤1091 \le X_i \le 10^9
  • All input values are integers.

样例 1 解释:
第 1 个人到第 2 个人的距离为 44,到第 3 个人的距离为 66,因此其到其他所有人的距离均不小于 DD。故第 1 个人“独立于众人”。
第 2 个人到第 3 个人的距离为 22,因此第 2 个人不“独立于众人”。
同理,第 3 个人到第 2 个人的距离也为 22,因此第 3 个人也不“独立于众人”。

综上,仅有第 1 个人“独立于众人”。

样例 2 解释:
可能存在位于同一坐标的多人。此外,若无人“独立于众人”,则第二行应为空行。

样例 3 解释:
按升序输出所有“独立于众人”的人的编号。

约束条件

  • 2≤N≤1002 \le N \le 100
  • 1≤D≤1091 \le D \le 10^9
  • 1≤Xi≤1091 \le X_i \le 10^9
  • 所有输入值均为整数。

输入解题思路,AI测评打分。不知道怎么写?

首页