分数: 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