← 返回题目列表

AtCoder · abc312_h

Ex. 核弹

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

高桥将决定昵称 N 人、人 1,\ldots,N.

人 i 想要一个昵称 S_i。 为了避免给多个人起相同的昵称,他将按如下方式决定他们的昵称:

  • 对于每个 i=1,\ldots,N 按顺序,决定人 i的昵称如下:
    • 初始化变量 k_i 与 1.
    • 重复递增 k_i 一会儿 k_i- 时间重复 S_i 是某人的昵称。
    • 让人 i的昵称是 k_i- 时间重复 S_i.

查找 k_1,\ldots,和 k_N 决定昵称后 N 人。

约束

  • N \geq 1
  • S_i 是长度至少为 1 由小写英文字母组成。
  • 的长度总和 S_i 最多是 2\times 10^5.

输入

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

N
S_1
\vdots
S_N

输出

打印 k_1,\ldots,和 k_N 因决定昵称而产生 N 人们通过程序中的问题陈述。


示例输入 1

3
snuke
snuke
rng

示例输出 1

1 2 1
  • 首先,他决定人 1的昵称。
    • 让 k_1=1.
    • 的 树的 k_1- 时间重复 S_1 is snuke,这不是任何人的昵称,所以人 1的昵称设置为 snuke.
  • 接下来,他决定人 2的昵称。
    • 让 k_2=1.
    • 的 树的 k_2- 时间重复 S_2 is snuke,这已经是人的昵称 1,所以递增 k_2 由一做起 2.
    • 的 树的 k_2- 时间重复 S_2 is snukesnuke,这不是任何人的昵称,所以人 2的昵称设置为 snukesnuke.
  • 最后,他决定人 3的昵称。
    • 让 k_3=1.
    • 的 树的 k_3- 时间重复 S_3 is rng,这不是任何人的昵称,所以人 3的昵称设置为 rng.

因此, 总共使用了 k_1, k_2,和 k_3 结果 1, 2,和 1。


示例输入 2

4
aa
a
a
aaa

示例输出 2

1 1 3 2
  • 人 1的昵称设置为 aa.
  • 人 2的昵称设置为 a.
  • 人 3的昵称设置为 aaa,因为 a 和 aa 已经是别人的昵称了。
  • 人 4的昵称设置为 aaaaaa,因为 aaa 已经是别人的昵称了。

示例输入 3

5
x
x
x
x
x

示例输出 3

1 2 3 4 5