{"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$ 中选择一个任意元素，并改变其二进制表示中的一个任意数位。结果数不能是改变前集合 $A$ 中的元素。\n\n例如，数字 $5$ 的二进制是 $0101_2$。通过一次操作，它可以变成 $13=1101_2$、$1=0001_2$、$7=0111_2$ 或 $4=0100_2$。\n\n确定一系列操作，通过这些操作集合 $A$ 变得和集合 $B$ 相等。如果两个集合大小相同，并且集合 $A$ 中没有不属于集合 $B$ 的元素，则认为两个集合是相等的。\n\n注意：操作的数量不必是最小的，但必须满足任务的限制。\n\n## Input\n\n第一行包含一个整数 $N$（$1 \\le N \\le 2^{15}$），集合 $A$ 和 $B$ 的大小。\n\n第二行包含 $N$ 个不同的整数 $a_i$（$0 \\le a_i < 2^{15}$），表示集合 $A$ 的元素。\n\n第二行包含 $N$ 个不同的整数 $b_i$（$0 \\le b_i < 2^{15}$），表示集合 $B$ 的元素。\n\n## Output\n\n第一行输出操作的数目，不超过 $2^{19}$。\n\n接下来若干行，每行输出 $x,y$（$0 \\le x, y < 2^{15}$），表示将集合 $A$ 中的 $x$ 修改为 $y$。$x$ 和 $y$ 在二进制位中只能有一位不同。并且，必须满足 $x\\in A$，$y\\not \\in A$。\n\n[samples]\n\n## Background\n\n**译自 [COCI 2023/2024 Contest #5](https://hsin.hr/coci/archive/2023_2024) T2「[Bitovi](https://hsin.hr/coci/archive/2023_2024/contest5_tasks.pdf)」**\n\n## Note\n\n### 样例解释 1\n\n如果我们先操作 $0\\ 1$，再操作 $1\\ 3$，两次操作间，集合 $A$ 将有两个相同的元素，这是不被允许的。另一种可能的方案是 $2\\ 3$，$0\\ 2$。\n\n### 样例解释 2\n\n$31=11111_2$。按照从最低有效位到最高有效位修改，依次可以得到 $30,28,24,16$ 和 $0$。在所有的操作后，$A$ 和 $B$ 相同。\n\n### 子任务\n\n| Subtask | Points | Constraints |\n| :--: | :--: | :--: |\n| 1 | 10 | $a_i,b_i \\le 2^{14}$ |\n| 2 | 15 | $N \\le 7$ | \n| 3 | 30 | $N \\le 2^7$ |\n| 4 | 15 | 无额外限制 |","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10258","tags":["2023","Special Judge","位运算","构造","COCI（克罗地亚）"],"sample_group":[["3\n0 1 2\n1 2 3","2\n1 3\n0 1"],["3\n4 8 31\n0 4 8","5\n31 30\n30 28\n28 24\n24 16\n16 0"],["5\n0 1 2 4 5\n7 6 5 3 2","9\n1 3\n3 7\n0 1\n1 0\n2 6\n0 2\n7 3\n5 7\n4 5"]],"created_at":"2026-03-03 11:09:25"}}