AT_abc485_c.Different Neighbor

普及-

通过率:0%

时间限制:2.00s

内存限制:1024MB

AC君温馨提醒

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

题目描述

There is one point at each of the coordinates 1,2,…,N1, 2, \ldots, N on a number line, and the point at coordinate ii is called point ii.

Each point has a color, and the color of point ii is CiC_i. Here, at least two distinct values appear in C1,C2,…,CNC_1, C_2, \ldots, C_N.

For each i=1,2,…,Ni = 1, 2, \ldots, N, find the distance from point ii to the nearest point whose color is different from that of point ii.

在一条数轴上,坐标 1,2,…,N1, 2, \ldots, N 处各有一个点,坐标为 ii 的点称为点 ii。

每个点都有一个颜色,点 ii 的颜色为 CiC_i。其中,C1,C2,…,CNC_1, C_2, \ldots, C_N 中至少出现两个不同的值。

对每个 i=1,2,…,Ni = 1, 2, \ldots, N,求点 ii 到与其颜色不同的最近点的距离。

输入格式

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

NN
C1C_1 C2C_2 …\ldots CNC_N

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

NN
C1C_1 C2C_2 …\ldots CNC_N

输出格式

Print the answers for i=1,2,…,Ni = 1, 2, \ldots, N in this order, separated by spaces.

按 i=1,2,…,Ni = 1, 2, \ldots, 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 11, the nearest to point 11 is point 33, and its distance from point 11 is 22.

Among the points whose color is different from that of point 22, the nearest to point 22 is point 33, and its distance from point 22 is 11.

Among the points whose color is different from that of point 33, the nearest to point 33 are points 22 and 44, and their distance from point 33 is 11.

Among the points whose color is different from that of point 44, the nearest to point 44 is point 33, and its distance from point 44 is 11.

Among the points whose color is different from that of point 55, the nearest to point 55 is point 33, and its distance from point 55 is 22.

Among the points whose color is different from that of point 66, the nearest to point 66 is point 33, and its distance from point 66 is 33.

Thus, print 2,1,1,1,2,32, 1, 1, 1, 2, 3 in this order, separated by spaces.

Constraints

  • 2≤N≤3×1052 \leq N \leq 3 \times 10^5
  • 1≤Ci≤N1 \leq C_i \leq N
  • At least two distinct values appear in C1,C2,…,CNC_1, C_2, \ldots, C_N.
  • All input values are integers.

样例 1 解释:
在所有颜色与点 11 不同的点中,距离点 11 最近的是点 33,其到点 11 的距离为 22。

在所有颜色与点 22 不同的点中,距离点 22 最近的是点 33,其到点 22 的距离为 11。

在所有颜色与点 33 不同的点中,距离点 33 最近的是点 22 和点 44,它们到点 33 的距离均为 11。

在所有颜色与点 44 不同的点中,距离点 44 最近的是点 33,其到点 44 的距离为 11。

在所有颜色与点 55 不同的点中,距离点 55 最近的是点 33,其到点 55 的距离为 22。

在所有颜色与点 66 不同的点中,距离点 66 最近的是点 33,其到点 66 的距离为 33。

因此,按此顺序输出 2,1,1,1,2,32, 1, 1, 1, 2, 3,各数之间用空格分隔。

约束条件

  • 2≤N≤3×1052 \leq N \leq 3 \times 10^5
  • 1≤Ci≤N1 \leq C_i \leq N
  • C1,C2,…,CNC_1, C_2, \ldots, C_N 中至少出现两个不同的值。
  • 所有输入值均为整数。

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

首页