F. AND-permutations

Codeforces

IDCF909F

Time2000ms

Memory256MB

Difficulty—

constructive algorithms

English · Original

Chinese · Translation

Formal · Original

Given an integer _N_, find two permutations: 1. Permutation _p_ of numbers from 1 to _N_ such that _p__i_ ≠ _i_ and _p__i_ & _i_ = 0 for all _i_ = 1, 2, ..., _N_. 2. Permutation _q_ of numbers from 1 to _N_ such that _q__i_ ≠ _i_ and _q__i_ & _i_ ≠ 0 for all _i_ = 1, 2, ..., _N_. & is the [bitwise AND operation](https://en.wikipedia.org/wiki/Bitwise_operation#AND). ## Input The input consists of one line containing a single integer _N_ (1 ≤ _N_ ≤ 105). ## Output For each subtask, if the required permutation doesn't exist, output a single line containing the word "_NO_"; otherwise output the word "_YES_" in the first line and _N_ elements of the permutation, separated by spaces, in the second line. If there are several possible permutations in a subtask, output any of them. [samples]

给定一个整数 $N$，找到两个排列： $\&$ 是按位与运算。输入包含一行，包含一个整数 $N$（$1 ≤ N ≤ 10^5$）。对于每个子任务，如果所需的排列不存在，则输出一行包含单词 "_NO_"；否则在第一行输出单词 "_YES_"，并在第二行输出排列的 $N$ 个元素，元素之间用空格分隔。如果某个子任务存在多个可能的排列，输出任意一个即可。 ## Input 输入包含一行，包含一个整数 $N$（$1 ≤ N ≤ 10^5$）。 ## Output 对于每个子任务，如果所需的排列不存在，则输出一行包含单词 "_NO_"；否则在第一行输出单词 "_YES_"，并在第二行输出排列的 $N$ 个元素，元素之间用空格分隔。如果某个子任务存在多个可能的排列，输出任意一个即可。 [samples]

**Definitions** Let $ N \in \mathbb{Z} $ with $ 1 \leq N \leq 10^5 $. Let $ P = (p_1, p_2, \dots, p_N) $ be a permutation of $ \{1, 2, \dots, N\} $. **Constraints** Find two permutations $ P_1 $ and $ P_2 $ of $ \{1, 2, \dots, N\} $ such that: $$ p_{1,i} \& p_{2,i} = c_i \quad \text{for all } i \in \{1, \dots, N\} $$ for some specified sequence $ c = (c_1, \dots, c_N) $ — **but no such $ c $ is provided in the input**. **Objective** Given only $ N $, output: - "_NO_" if no pair of permutations $ (P_1, P_2) $ exists satisfying an implicit condition (unspecified). - "_YES_" followed by any valid $ P_1 $ and $ P_2 $ if such a pair exists. **Note**: The problem statement is incomplete — the target bitwise AND values $ c_i $ are not given. Without them, the condition is ill-defined.

Samples

Input #1

Output #1

NO
NO

Input #2

Output #2

YES
6 5 4 3 2 1 
YES
3 6 2 5 1 4

API Response (JSON)

{
  "problem": {
    "name": "F. AND-permutations",
    "description": {
      "content": "Given an integer _N_, find two permutations: 1.  Permutation _p_ of numbers from 1 to _N_ such that _p__i_ ≠ _i_ and _p__i_ & _i_ = 0 for all _i_ = 1, 2, ..., _N_. 2.  Permutation _q_ of numbers from",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF909F"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Given an integer _N_, find two permutations:\n\n1.  Permutation _p_ of numbers from 1 to _N_ such that _p__i_ ≠ _i_ and _p__i_ & _i_ = 0 for all _i_ = 1, 2, ..., _N_.\n2.  Permutation _q_ of numbers from...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "给定一个整数 $N$，找到两个排列：\n\n$\\&$ 是按位与运算。\n\n输入包含一行，包含一个整数 $N$（$1 ≤ N ≤ 10^5$）。\n\n对于每个子任务，如果所需的排列不存在，则输出一行包含单词 \"_NO_\"；否则在第一行输出单词 \"_YES_\"，并在第二行输出排列的 $N$ 个元素，元素之间用空格分隔。如果某个子任务存在多个可能的排列，输出任意一个即可。\n\n## Input\n\n输入包含一行，包...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ N \\in \\mathbb{Z} $ with $ 1 \\leq N \\leq 10^5 $.  \nLet $ P = (p_1, p_2, \\dots, p_N) $ be a permutation of $ \\{1, 2, \\dots, N\\} $.  \n\n**Constraints**  \nFind two permutations $ P_...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments