C. Sorting by Subsequences

Codeforces

IDCF844C

Time1000ms

Memory256MB

Difficulty—

dfs and similarmath

English · Original

Chinese · Translation

Formal · Original

You are given a sequence _a_1, _a_2, ..., _a__n_ consisting of **different** integers. It is required to split this sequence into the **maximum** number of subsequences such that after sorting integers in each of them in increasing order, the total sequence also will be sorted in increasing order. Sorting integers in a subsequence is a process such that the numbers included in a subsequence are ordered in increasing order, and the numbers which are not included in a subsequence don't change their places. Every element of the sequence must appear in exactly one subsequence. ## Input The first line of input data contains integer _n_ (1 ≤ _n_ ≤ 105) — the length of the sequence. The second line of input data contains _n_ different integers _a_1, _a_2, ..., _a__n_ ( - 109 ≤ _a__i_ ≤ 109) — the elements of the sequence. It is guaranteed that all elements of the sequence are distinct. ## Output In the first line print the maximum number of subsequences _k_, which the original sequence can be split into while fulfilling the requirements. In the next _k_ lines print the description of subsequences in the following format: the number of elements in subsequence _c__i_ (0 < _c__i_ ≤ _n_), then _c__i_ integers _l_1, _l_2, ..., _l__c__i_ (1 ≤ _l__j_ ≤ _n_) — indices of these elements in the original sequence. Indices could be printed in any order. Every index from 1 to _n_ must appear in output **exactly once**. If there are several possible answers, print any of them. [samples] ## Note In the first sample output: After sorting the first subsequence we will get sequence 1 2 3 6 5 4. Sorting the second subsequence changes nothing. After sorting the third subsequence we will get sequence 1 2 3 4 5 6. Sorting the last subsequence changes nothing.

给定一个由*不同*整数组成的序列 #cf_span[a1, a2, ..., an]。要求将该序列划分为*最大*数量的子序列，使得将每个子序列中的整数按升序排序后，整个序列也会按升序排列。对一个子序列进行排序是指：该子序列中包含的数字按升序排列，而未包含在该子序列中的数字保持原有位置不变。序列中的每个元素必须恰好属于一个子序列。输入的第一行包含整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 105]) —— 序列的长度。第二行包含 #cf_span[n] 个不同的整数 #cf_span[a1, a2, ..., an] (#cf_span[ - 109 ≤ ai ≤ 109]) —— 序列的元素。保证序列中所有元素互不相同。第一行输出最大子序列数量 #cf_span[k]，使得原序列能按要求划分为 #cf_span[k] 个子序列。接下来的 #cf_span[k] 行，每行描述一个子序列：先输出该子序列的元素个数 #cf_span[ci] (#cf_span[0 < ci ≤ n])，然后输出 #cf_span[ci] 个整数 #cf_span[l1, l2, ..., lci] (#cf_span[1 ≤ lj ≤ n]) —— 这些元素在原序列中的下标。下标可以按任意顺序输出，但从 #cf_span[1] 到 #cf_span[n] 的每个下标必须在输出中恰好出现一次。如果有多个可能的答案，输出任意一个即可。在第一个样例输出中：对第一个子序列排序后，得到序列 #cf_span[1 2 3 6 5 4]。对第二个子序列排序不会改变任何内容。对第三个子序列排序后，得到序列 #cf_span[1 2 3 4 5 6]。对最后一个子序列排序不会改变任何内容。 ## Input 输入的第一行包含整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 105]) —— 序列的长度。第二行包含 #cf_span[n] 个不同的整数 #cf_span[a1, a2, ..., an] (#cf_span[ - 109 ≤ ai ≤ 109]) —— 序列的元素。保证序列中所有元素互不相同。 ## Output 第一行输出最大子序列数量 #cf_span[k]，使得原序列能按要求划分为 #cf_span[k] 个子序列。接下来的 #cf_span[k] 行，每行描述一个子序列：先输出该子序列的元素个数 #cf_span[ci] (#cf_span[0 < ci ≤ n])，然后输出 #cf_span[ci] 个整数 #cf_span[l1, l2, ..., lci] (#cf_span[1 ≤ lj ≤ n]) —— 这些元素在原序列中的下标。下标可以按任意顺序输出，但从 #cf_span[1] 到 #cf_span[n] 的每个下标必须在输出中恰好出现一次。如果有多个可能的答案，输出任意一个即可。 [samples] ## Note 在第一个样例输出中：对第一个子序列排序后，得到序列 #cf_span[1 2 3 6 5 4]。对第二个子序列排序不会改变任何内容。对第三个子序列排序后，得到序列 #cf_span[1 2 3 4 5 6]。对最后一个子序列排序不会改变任何内容。

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the length of the sequence. Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of distinct integers. Let $ P = \{1, 2, \dots, n\} $ be the set of indices. A *subsequence partition* is a collection of disjoint non-empty index sets $ S_1, S_2, \dots, S_k \subseteq P $ such that $ \bigcup_{i=1}^k S_i = P $. For each subsequence $ S_i $, let $ A|_{S_i} $ denote the subsequence of $ A $ indexed by $ S_i $. Let $ \text{sort}(A|_{S_i}) $ denote the sequence $ A|_{S_i} $ sorted in increasing order. Define the *reconstructed sequence* after sorting all subsequences as the sequence $ B = (b_1, b_2, \dots, b_n) $, where for each position $ j \in P $, if $ j \in S_i $, then $ b_j $ is the element of $ \text{sort}(A|_{S_i}) $ that occupies the same relative position in $ S_i $ as $ j $ does in the sorted order of $ S_i $. **Constraints** 1. $ 1 \le n \le 10^5 $ 2. $ a_i \in \mathbb{Z} $, $ -10^9 \le a_i \le 10^9 $, and all $ a_i $ are distinct. 3. The reconstructed sequence $ B $ must satisfy $ b_1 \le b_2 \le \dots \le b_n $ (i.e., non-decreasing). **Objective** Maximize $ k $, the number of subsequences in the partition, such that the reconstructed sequence $ B $ is non-decreasing. Output: - The maximum $ k $. - For each $ i \in \{1, \dots, k\} $: - The size $ c_i = |S_i| $, - The set of indices $ S_i = \{l_1, l_2, \dots, l_{c_i}\} \subseteq P $, in any order. **Note**: The partition must cover all indices exactly once.

Samples

Input #1

6
3 2 1 6 5 4

Output #1

Input #2

6
83 -75 -49 11 37 62

Output #2

1
6 1 2 3 4 5 6

API Response (JSON)

{
  "problem": {
    "name": "C. Sorting by Subsequences",
    "description": {
      "content": "You are given a sequence _a_1, _a_2, ..., _a__n_ consisting of **different** integers. It is required to split this sequence into the **maximum** number of subsequences such that after sorting integer",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF844C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given a sequence _a_1, _a_2, ..., _a__n_ consisting of **different** integers. It is required to split this sequence into the **maximum** number of subsequences such that after sorting integer...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "给定一个由*不同*整数组成的序列 #cf_span[a1, a2, ..., an]。要求将该序列划分为*最大*数量的子序列，使得将每个子序列中的整数按升序排序后，整个序列也会按升序排列。\n\n对一个子序列进行排序是指：该子序列中包含的数字按升序排列，而未包含在该子序列中的数字保持原有位置不变。\n\n序列中的每个元素必须恰好属于一个子序列。\n\n输入的第一行包含整数 #cf_span[n] (#cf_s...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the length of the sequence.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of distinct integers.  \nLet $ P = \\{1, 2, \\dots, n\\} $ be the set of indi...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments