AT_abc485_c.Different Neighbor
普及-
通过率:0%
时间限制:2.00s
内存限制:1024MB
AC君温馨提醒
该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
There is one point at each of the coordinates 1,2,…,N on a number line, and the point at coordinate i is called point i.
Each point has a color, and the color of point i is Ci. Here, at least two distinct values appear in C1,C2,…,CN.
For each i=1,2,…,N, find the distance from point i to the nearest point whose color is different from that of point i.
在一条数轴上,坐标 1,2,…,N 处各有一个点,坐标为 i 的点称为点 i。
每个点都有一个颜色,点 i 的颜色为 Ci。其中,C1,C2,…,CN 中至少出现两个不同的值。
对每个 i=1,2,…,N,求点 i 到与其颜色不同的最近点的距离。
输入格式
The input is given from Standard Input in the following format:
N
C1 C2 … CN
输入从标准输入中按以下格式给出:
N
C1 C2 … CN
输出格式
Print the answers for i=1,2,…,N in this order, separated by spaces.
按 i=1,2,…,N 的顺序输出答案,用空格分隔。
输入输出样例
输入#1
6 1 1 2 3 3 3
输出#1
2 1 1 1 2 3
输入#2
7 4 2 3 3 3 4 4
输出#2
1 1 1 2 1 1 2
说明/提示
Sample 1 Explanation:
Among the points whose color is different from that of point 1, the nearest to point 1 is point 3, and its distance from point 1 is 2.
Among the points whose color is different from that of point 2, the nearest to point 2 is point 3, and its distance from point 2 is 1.
Among the points whose color is different from that of point 3, the nearest to point 3 are points 2 and 4, and their distance from point 3 is 1.
Among the points whose color is different from that of point 4, the nearest to point 4 is point 3, and its distance from point 4 is 1.
Among the points whose color is different from that of point 5, the nearest to point 5 is point 3, and its distance from point 5 is 2.
Among the points whose color is different from that of point 6, the nearest to point 6 is point 3, and its distance from point 6 is 3.
Thus, print 2,1,1,1,2,3 in this order, separated by spaces.
Constraints
- 2≤N≤3×105
- 1≤Ci≤N
- At least two distinct values appear in C1,C2,…,CN.
- All input values are integers.
样例 1 解释:
在所有颜色与点 1 不同的点中,距离点 1 最近的是点 3,其到点 1 的距离为 2。
在所有颜色与点 2 不同的点中,距离点 2 最近的是点 3,其到点 2 的距离为 1。
在所有颜色与点 3 不同的点中,距离点 3 最近的是点 2 和点 4,它们到点 3 的距离均为 1。
在所有颜色与点 4 不同的点中,距离点 4 最近的是点 3,其到点 4 的距离为 1。
在所有颜色与点 5 不同的点中,距离点 5 最近的是点 3,其到点 5 的距离为 2。
在所有颜色与点 6 不同的点中,距离点 6 最近的是点 3,其到点 6 的距离为 3。
因此,按此顺序输出 2,1,1,1,2,3,各数之间用空格分隔。
约束条件
- 2≤N≤3×105
- 1≤Ci≤N
- C1,C2,…,CN 中至少出现两个不同的值。
- 所有输入值均为整数。
输入解题思路,AI测评打分。不知道怎么写?