E. Mike and code of a permutation

Codeforces

IDCF798E

Time4000ms

Memory512MB

Difficulty—

constructive algorithmsdata structuresgraphssortings

English · Original

Chinese · Translation

Formal · Original

Mike has discovered a new way to encode permutations. If he has a permutation _P_ = \[_p_1, _p_2, ..., _p__n_\], he will encode it in the following way: Denote by _A_ = \[_a_1, _a_2, ..., _a__n_\] a sequence of length _n_ which will represent the code of the permutation. For each _i_ from 1 to _n_ sequentially, he will choose the smallest unmarked _j_ (1 ≤ _j_ ≤ _n_) such that _p__i_ < _p__j_ and will assign to _a__i_ the number _j_ (in other words he performs _a__i_ = _j_) and will mark _j_. If there is no such _j_, he'll assign to _a__i_ the number - 1 (he performs _a__i_ = - 1). Mike forgot his original permutation but he remembers its code. Your task is simple: find **any** permutation such that its code is the same as the code of Mike's original permutation. You may assume that there will always be at least one valid permutation. ## Input The first line contains single integer _n_ (1 ≤ _n_ ≤ 500 000) — length of permutation. The second line contains _n_ space-separated integers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ _n_ or _a__i_ = - 1) — the code of Mike's permutation. You may assume that all positive values from _A_ are different. ## Output In first and only line print _n_ numbers _p_1, _p_2, ..., _p__n_ (1 ≤ _p__i_ ≤ _n_) — a permutation _P_ which has the same code as the given one. Note that numbers in permutation are distinct. [samples] ## Note For the permutation from the first example: _i_ = 1, the smallest _j_ is 2 because _p_2 = 6 > _p_1 = 2. _i_ = 2, there is no _j_ because _p_2 = 6 is the greatest element in the permutation. _i_ = 3, the smallest _j_ is 1 because _p_1 = 2 > _p_3 = 1. _i_ = 4, the smallest _j_ is 5 (2 was already marked) because _p_5 = 5 > _p_4 = 4. _i_ = 5, there is no _j_ because 2 is already marked. _i_ = 6, the smallest _j_ is 4 because _p_4 = 4 > _p_6 = 3.

Mike 发现了一种新的排列编码方式。如果他有一个排列 #cf_span[P = [p1, p2, ..., pn]]，他会按以下方式编码它：记 #cf_span[A = [a1, a2, ..., an]] 为一个长度为 #cf_span[n] 的序列，表示该排列的编码。对于每个 #cf_span[i] 从 #cf_span[1] 到 #cf_span[n] 依次处理，他会选择最小的未标记的 #cf_span[j]（#cf_span[1 ≤ j ≤ n]），使得 #cf_span[pi < pj]，并将 #cf_span[ai] 设为 #cf_span[j]（即执行 #cf_span[ai = j]），然后标记 #cf_span[j]。如果没有这样的 #cf_span[j]，他会将 #cf_span[ai] 设为 #cf_span[ - 1]（即执行 #cf_span[ai = - 1]）。 Mike 忘记了他的原始排列，但他记得它的编码。你的任务很简单：找到 *任意一个* 排列，使其编码与 Mike 原始排列的编码相同。你可以假定至少存在一个有效的排列。第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 500 000]）——排列的长度。第二行包含 #cf_span[n] 个用空格分隔的整数 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ n] 或 #cf_span[ai = - 1]）——Mike 排列的编码。你可以假定 #cf_span[A] 中所有正值互不相同。在第一行且仅一行中，输出 #cf_span[n] 个数字 #cf_span[p1, p2, ..., pn]（#cf_span[1 ≤ pi ≤ n]）——一个与给定编码相同的排列 #cf_span[P]。注意排列中的数字互不相同。对于第一个示例中的排列： #cf_span[i = 1]，最小的 #cf_span[j] 是 #cf_span[2]，因为 #cf_span[p2 = 6 > p1 = 2]。 #cf_span[i = 2]，不存在这样的 #cf_span[j]，因为 #cf_span[p2 = 6] 是排列中的最大元素。 #cf_span[i = 3]，最小的 #cf_span[j] 是 #cf_span[1]，因为 #cf_span[p1 = 2 > p3 = 1]。 #cf_span[i = 4]，最小的 #cf_span[j] 是 #cf_span[5]（#cf_span[2] 已被标记），因为 #cf_span[p5 = 5 > p4 = 4]。 #cf_span[i = 5]，不存在这样的 #cf_span[j]，因为 #cf_span[2] 已被标记。 #cf_span[i = 6]，最小的 #cf_span[j] 是 #cf_span[4]，因为 #cf_span[p4 = 4 > p6 = 3]。 ## Input 第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 500 000]）——排列的长度。第二行包含 #cf_span[n] 个用空格分隔的整数 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ n] 或 #cf_span[ai = - 1]）——Mike 排列的编码。你可以假定 #cf_span[A] 中所有正值互不相同。 ## Output 在第一行且仅一行中，输出 #cf_span[n] 个数字 #cf_span[p1, p2, ..., pn]（#cf_span[1 ≤ pi ≤ n]）——一个与给定编码相同的排列 #cf_span[P]。注意排列中的数字互不相同。 [samples] ## Note 对于第一个示例中的排列：#cf_span[i = 1]，最小的 #cf_span[j] 是 #cf_span[2]，因为 #cf_span[p2 = 6 > p1 = 2]。#cf_span[i = 2]，不存在这样的 #cf_span[j]，因为 #cf_span[p2 = 6] 是排列中的最大元素。#cf_span[i = 3]，最小的 #cf_span[j] 是 #cf_span[1]，因为 #cf_span[p1 = 2 > p3 = 1]。#cf_span[i = 4]，最小的 #cf_span[j] 是 #cf_span[5]（#cf_span[2] 已被标记），因为 #cf_span[p5 = 5 > p4 = 4]。#cf_span[i = 5]，不存在这样的 #cf_span[j]，因为 #cf_span[2] 已被标记。#cf_span[i = 6]，最小的 #cf_span[j] 是 #cf_span[4]，因为 #cf_span[p4 = 4 > p6 = 3]。

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the length of the permutation. Let $ A = (a_1, a_2, \dots, a_n) $ be the given code, where each $ a_i \in \{-1\} \cup \{1, 2, \dots, n\} $, and all positive values in $ A $ are distinct. Let $ P = (p_1, p_2, \dots, p_n) $ be a permutation of $ \{1, 2, \dots, n\} $ to be determined. **Constraints** For each $ i \in \{1, \dots, n\} $: - If $ a_i = -1 $, then there is no unmarked $ j $ such that $ p_i < p_j $. - If $ a_i = j > 0 $, then: 1. $ j $ is the smallest unmarked index at step $ i $ such that $ p_i < p_j $, 2. $ j $ is unmarked before step $ i $, 3. $ j $ is marked after step $ i $. **Objective** Find any permutation $ P = (p_1, \dots, p_n) $ satisfying the above constraints.

Samples

Input #1

6
2 -1 1 5 -1 4

Output #1

2 6 1 4 5 3

Input #2

8
2 -1 4 -1 6 -1 8 -1

Output #2

1 8 2 7 3 6 4 5

API Response (JSON)

{
  "problem": {
    "name": "E. Mike and code of a permutation",
    "description": {
      "content": "Mike has discovered a new way to encode permutations. If he has a permutation _P_ = \\[_p_1, _p_2, ..., _p__n_\\], he will encode it in the following way: Denote by _A_ = \\[_a_1, _a_2, ..., _a__n_\\] a ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF798E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Mike has discovered a new way to encode permutations. If he has a permutation _P_ = \\[_p_1, _p_2, ..., _p__n_\\], he will encode it in the following way:\n\nDenote by _A_ = \\[_a_1, _a_2, ..., _a__n_\\] a ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Mike 发现了一种新的排列编码方式。如果他有一个排列 #cf_span[P = [p1, p2, ..., pn]]，他会按以下方式编码它：\n\n记 #cf_span[A = [a1, a2, ..., an]] 为一个长度为 #cf_span[n] 的序列，表示该排列的编码。对于每个 #cf_span[i] 从 #cf_span[1] 到 #cf_span[n] 依次处理，他会选择最小的未标记的...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the length of the permutation.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be the given code, where each $ a_i \\in \\{-1\\} \\cup \\{1, 2, \\dots, n\\} $, and all po...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments