[COCI 2023/2024 #5] Bitovi

Luogu

IDLGP10258

Time1000ms

Memory512MB

DifficultyP4

2023Special Judge位运算构造COCI（克罗地亚）

哪个先出现，鸡还是蛋？作为一个百万富翁活上一百年好，还是贫穷中度过七天好？如何成为国际象棋大师？如何拉起百叶窗？如何通过期末考试？如何训练龙？这些都是一些有趣的问题，我们可以在竞赛结束后再去思考，但现在我们提出一个不那么有趣的计算机科学问题。给定两组数集 $A$ 和 $B$，大小均为 $N$。每次操作，你可以从集合 $A$ 中选择一个任意元素，并改变其二进制表示中的一个任意数位。结果数不能是改变前集合 $A$ 中的元素。例如，数字 $5$ 的二进制是 $0101_2$。通过一次操作，它可以变成 $13=1101_2$、$1=0001_2$、$7=0111_2$ 或 $4=0100_2$。确定一系列操作，通过这些操作集合 $A$ 变得和集合 $B$ 相等。如果两个集合大小相同，并且集合 $A$ 中没有不属于集合 $B$ 的元素，则认为两个集合是相等的。注意：操作的数量不必是最小的，但必须满足任务的限制。 ## Input 第一行包含一个整数 $N$（$1 \le N \le 2^{15}$），集合 $A$ 和 $B$ 的大小。第二行包含 $N$ 个不同的整数 $a_i$（$0 \le a_i < 2^{15}$），表示集合 $A$ 的元素。第二行包含 $N$ 个不同的整数 $b_i$（$0 \le b_i < 2^{15}$），表示集合 $B$ 的元素。 ## Output 第一行输出操作的数目，不超过 $2^{19}$。接下来若干行，每行输出 $x,y$（$0 \le x, y < 2^{15}$），表示将集合 $A$ 中的 $x$ 修改为 $y$。$x$ 和 $y$ 在二进制位中只能有一位不同。并且，必须满足 $x\in A$，$y\not \in A$。 [samples] ## Background **译自 [COCI 2023/2024 Contest #5](https://hsin.hr/coci/archive/2023_2024) T2「[Bitovi](https://hsin.hr/coci/archive/2023_2024/contest5_tasks.pdf)」** ## Note ### 样例解释 1 如果我们先操作 $0\ 1$，再操作 $1\ 3$，两次操作间，集合 $A$ 将有两个相同的元素，这是不被允许的。另一种可能的方案是 $2\ 3$，$0\ 2$。 ### 样例解释 2 $31=11111_2$。按照从最低有效位到最高有效位修改，依次可以得到 $30,28,24,16$ 和 $0$。在所有的操作后，$A$ 和 $B$ 相同。 ### 子任务 | Subtask | Points | Constraints | | :--: | :--: | :--: | | 1 | 10 | $a_i,b_i \le 2^{14}$ | | 2 | 15 | $N \le 7$ | | 3 | 30 | $N \le 2^7$ | | 4 | 15 | 无额外限制 |

Samples

Input #1

3
0 1 2
1 2 3

Output #1

2
1 3
0 1

Input #2

3
4 8 31
0 4 8

Output #2

Input #3

5
0 1 2 4 5
7 6 5 3 2

Output #3

API Response (JSON)

{
  "problem": {
    "name": "[COCI 2023/2024 #5] Bitovi",
    "description": {
      "content": "哪个先出现，鸡还是蛋？作为一个百万富翁活上一百年好，还是贫穷中度过七天好？如何成为国际象棋大师？如何拉起百叶窗？如何通过期末考试？如何训练龙？这些都是一些有趣的问题，我们可以在竞赛结束后再去思考，但现在我们提出一个不那么有趣的计算机科学问题。 给定两组数集 $A$ 和 $B$，大小均为 $N$。每次操作，你可以从集合 $A$ 中选择一个任意元素，并改变其二进制表示中的一个任意数位。结果数不能是改",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10258"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "哪个先出现，鸡还是蛋？作为一个百万富翁活上一百年好，还是贫穷中度过七天好？如何成为国际象棋大师？如何拉起百叶窗？如何通过期末考试？如何训练龙？这些都是一些有趣的问题，我们可以在竞赛结束后再去思考，但现在我们提出一个不那么有趣的计算机科学问题。\n\n给定两组数集 $A$ 和 $B$，大小均为 $N$。每次操作，你可以从集合 $A$ 中选择一个任意元素，并改变其二进制表示中的一个任意数位。结果数不能是改...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments