B. Derangement

Codeforces

IDCF10097B

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

A permutation of n numbers is a sequence of integers from 1 to n where each number is occurred exactly once. If a permutation p1, p2, ..., pn has an index i such that pi = i, this index is called a fixed point. A derangement is a permutation without any fixed points. Let's denote the operation swap(a, b) as swapping elements on positions a and b. For the given permutation find the minimal number of swap operations needed to turn it into derangement. The first line contains an integer n (2 ≤ n ≤ 200000) — the number of elements in a permutation. The second line contains the elements of the permutation — n distinct integers from 1 to n. In the first line output a single integer k — the minimal number of swap operations needed to transform the permutation into derangement. In each of the next k lines output two integers ai and bi (1 ≤ ai, bi ≤ n) — the arguments of swap operations. If there are multiple possible solutions, output any of them. ## Input The first line contains an integer n (2 ≤ n ≤ 200000) — the number of elements in a permutation.The second line contains the elements of the permutation — n distinct integers from 1 to n. ## Output In the first line output a single integer k — the minimal number of swap operations needed to transform the permutation into derangement.In each of the next k lines output two integers ai and bi (1 ≤ ai, bi ≤ n) — the arguments of swap operations.If there are multiple possible solutions, output any of them. [samples]

**Definitions** Let $ n \in \mathbb{Z} $ with $ 2 \leq n \leq 200000 $. Let $ \pi = (\pi_1, \pi_2, \dots, \pi_n) $ be a permutation of $ \{1, 2, \dots, n\} $. A *fixed point* is an index $ i $ such that $ \pi_i = i $. A *derangement* is a permutation with no fixed points. **Constraints** - $ \pi $ is a bijection from $ \{1, \dots, n\} $ to $ \{1, \dots, n\} $. - The goal is to transform $ \pi $ into a derangement using the minimum number of transpositions (swaps). **Objective** Find the minimum number $ k $ of swap operations $ \text{swap}(a_i, b_i) $ such that the resulting permutation $ \pi' $ satisfies $ \pi'_i \neq i $ for all $ i \in \{1, \dots, n\} $, and output the sequence of swaps achieving this minimum.

API Response (JSON)

{
  "problem": {
    "name": "B. Derangement",
    "description": {
      "content": "A permutation of n numbers is a sequence of integers from 1 to n where each number is occurred exactly once. If a permutation p1, p2, ..., pn has an index i such that pi = i, this index is called a fi",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10097B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "A permutation of n numbers is a sequence of integers from 1 to n where each number is occurred exactly once. If a permutation p1, p2, ..., pn has an index i such that pi = i, this index is called a fi...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ with $ 2 \\leq n \\leq 200000 $.  \nLet $ \\pi = (\\pi_1, \\pi_2, \\dots, \\pi_n) $ be a permutation of $ \\{1, 2, \\dots, n\\} $.  \nA *fixed point* is an index $ i $ s...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments