C. Mahmoud and Ehab and the xor

Codeforces

IDCF862C

Time2000ms

Memory256MB

Difficulty—

constructive algorithms

English · Original

Chinese · Translation

Formal · Original

Mahmoud and Ehab are on the third stage of their adventures now. As you know, Dr. Evil likes sets. This time he won't show them any set from his large collection, but will ask them to create a new set to replenish his beautiful collection of sets. Dr. Evil has his favorite evil integer _x_. He asks Mahmoud and Ehab to find a set of _n_ distinct non-negative integers such the bitwise-xor sum of the integers in it is exactly _x_. Dr. Evil doesn't like big numbers, so any number in the set shouldn't be greater than 106. ## Input The only line contains two integers _n_ and _x_ (1 ≤ _n_ ≤ 105, 0 ≤ _x_ ≤ 105) — the number of elements in the set and the desired bitwise-xor, respectively. ## Output If there is no such set, print "NO" (without quotes). Otherwise, on the first line print "YES" (without quotes) and on the second line print _n_ distinct integers, denoting the elements in the set is any order. If there are multiple solutions you can print any of them. [samples] ## Note You can read more about the bitwise-xor operation here: [https://en.wikipedia.org/wiki/Bitwise_operation#XOR](https://en.wikipedia.org/wiki/Bitwise_operation#XOR) For the first sample . For the second sample .

Mahmoud 和 Ehab 正在进行他们冒险的第三阶段。正如你所知，Dr. Evil 喜欢集合。这一次，他不会向他们展示他庞大集合中的任何一个集合，而是要求他们创建一个新的集合来补充他美丽的集合收藏。 Dr. Evil 有一个他最喜欢的邪恶整数 $x$。他要求 Mahmoud 和 Ehab 找到一个包含 $n$ 个互不相同的非负整数的集合，使得集合中所有整数的按位异或和恰好为 $x$。Dr. Evil 不喜欢大数，因此集合中的每个数都不应超过 $10^6$。输入仅包含一行，两个整数 $n$ 和 $x$（$1 ≤ n ≤ 10^5$，$0 ≤ x ≤ 10^5$）——分别表示集合中元素的个数和期望的按位异或值。如果不存在这样的集合，请输出 "NO"（不含引号）。否则，第一行输出 "YES"（不含引号），第二行输出 $n$ 个互不相同的整数，表示集合中的元素，顺序任意。如果存在多个解，你可以输出其中任意一个。你可以在这里阅读更多关于按位异或操作的信息：https://en.wikipedia.org/wiki/Bitwise_operation#XOR 对于第一个样例。对于第二个样例。 ## Input 输入仅包含一行，两个整数 $n$ 和 $x$（$1 ≤ n ≤ 10^5$，$0 ≤ x ≤ 10^5$）——分别表示集合中元素的个数和期望的按位异或值。 ## Output 如果不存在这样的集合，请输出 "NO"（不含引号）。否则，第一行输出 "YES"（不含引号），第二行输出 $n$ 个互不相同的整数，表示集合中的元素，顺序任意。如果存在多个解，你可以输出其中任意一个。 [samples] ## Note 你可以在这里阅读更多关于按位异或操作的信息：https://en.wikipedia.org/wiki/Bitwise_operation#XOR 对于第一个样例。对于第二个样例。

**Definitions** Let $ n \in \mathbb{Z}^+ $, $ x \in \mathbb{Z}_{\geq 0} $, with $ 1 \leq n \leq 10^5 $, $ 0 \leq x \leq 10^5 $. Let $ S \subseteq \mathbb{Z}_{\geq 0} $ be a set of $ n $ distinct integers such that $ \max(S) \leq 10^6 $. **Constraints** 1. $ |S| = n $ 2. $ \bigoplus_{s \in S} s = x $ (bitwise XOR sum) 3. $ \forall s \in S, \, 0 \leq s \leq 10^6 $ 4. $ \forall s_1, s_2 \in S, \, s_1 \neq s_2 $ **Objective** Determine whether such a set $ S $ exists. If yes, output any such set; otherwise, output "NO".

Samples

Input #1

5 5

Output #1

YES
1 2 4 5 7

Input #2

3 6

Output #2

YES
1 2 5

API Response (JSON)

{
  "problem": {
    "name": "C. Mahmoud and Ehab and the xor",
    "description": {
      "content": "Mahmoud and Ehab are on the third stage of their adventures now. As you know, Dr. Evil likes sets. This time he won't show them any set from his large collection, but will ask them to create a new set",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF862C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Mahmoud and Ehab are on the third stage of their adventures now. As you know, Dr. Evil likes sets. This time he won't show them any set from his large collection, but will ask them to create a new set...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Mahmoud 和 Ehab 正在进行他们冒险的第三阶段。正如你所知，Dr. Evil 喜欢集合。这一次，他不会向他们展示他庞大集合中的任何一个集合，而是要求他们创建一个新的集合来补充他美丽的集合收藏。\n\nDr. Evil 有一个他最喜欢的邪恶整数 $x$。他要求 Mahmoud 和 Ehab 找到一个包含 $n$ 个互不相同的非负整数的集合，使得集合中所有整数的按位异或和恰好为 $x$。Dr. ...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $, $ x \\in \\mathbb{Z}_{\\geq 0} $, with $ 1 \\leq n \\leq 10^5 $, $ 0 \\leq x \\leq 10^5 $.  \nLet $ S \\subseteq \\mathbb{Z}_{\\geq 0} $ be a set of $ n $ distinct i...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments