CF569B.Inventory

普及-

通过率:0%

时间限制:1.00s

内存限制:256MB

AC君温馨提醒

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

题目描述

Companies always have a lot of equipment, furniture and other things. All of them should be tracked. To do this, there is an inventory number assigned with each item. It is much easier to create a database by using those numbers and keep the track of everything.

During an audit, you were surprised to find out that the items are not numbered sequentially, and some items even share the same inventory number! There is an urgent need to fix it. You have chosen to make the numbers of the items sequential, starting with 1. Changing a number is quite a time-consuming process, and you would like to make maximum use of the current numbering.

You have been given information on current inventory numbers for n items in the company. Renumber items so that their inventory numbers form a permutation of numbers from 1 to n by changing the number of as few items as possible. Let us remind you that a set of n numbers forms a permutation if all the numbers are in the range from 1 to n, and no two numbers are equal.

公司通常拥有大量设备、家具及其他物品,所有这些物品都需要进行跟踪管理。为此,每件物品都会被分配一个库存编号。利用这些编号建立数据库,可以更便捷地追踪所有物品。

在一次审计过程中,你惊讶地发现这些物品的编号并非连续,甚至有些物品共享相同的库存编号!亟需对此问题进行修正。你决定将物品编号调整为从 1 开始的连续序列。然而,修改编号是一项耗时的工作,因此你希望尽可能多地保留当前的编号。

你已获得公司中 $ n $ 件物品当前的库存编号信息。请重新为这些物品编号,使得其库存编号构成一个从 1 到 $ n $ 的排列(即:所有编号均落在区间 [1,n][1, n] 内,且任意两个编号互不相同),同时使需要修改编号的物品数量最少。需要提醒的是:当且仅当 $ n $ 个数全部位于 [1,n][1, n] 区间内且两两互异时,这组数才构成一个排列。

输入格式

The first line contains a single integer n — the number of items (1 ≤ n ≤ 105).

The second line contains n numbers _a_1, _a_2, ..., a__n (1 ≤ a__i ≤ 105) — the initial inventory numbers of the items.

第一行包含一个整数 nn —— 物品的数量(1 ≤ n ≤ 1051 ≤ n ≤ 10^5)。

第二行包含 nn 个数 a1, a2, ..., ana_1, a_2, ..., a_n(1 ≤ ai ≤ 1051 ≤ a_i ≤ 10^5)—— 各物品的初始库存编号。

输出格式

Print n numbers — the final inventory numbers of the items in the order they occur in the input. If there are multiple possible answers, you may print any of them.

输出 n 个数字——即物品在输入中出现顺序对应的最终库存数量。若存在多个可能的答案,输出任意一个即可。

输入输出样例

  • 输入#1

    3
    1 3 2

    输出#1

    1 3 2
  • 输入#2

    4
    2 2 3 3

    输出#2

    2 1 3 4
  • 输入#3

    1
    2

    输出#3

    1

说明/提示

In the first test the numeration is already a permutation, so there is no need to change anything.

In the second test there are two pairs of equal numbers, in each pair you need to replace one number.

In the third test you need to replace 2 by 1, as the numbering should start from one.

在第一个测试中,编号本身已经是一个排列,因此无需进行任何修改。

在第二个测试中,存在两对相等的数字;在每一对中,你需要将其中一个数字替换掉。

在第三个测试中,你需要将 2 替换为 1,因为编号应从 1 开始。

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

首页