有一个很简单的问题,你有 n 个数,其中 m 个数值出现了奇数次,剩下的数值都出现了偶数次,请你找出这 m 个数。
很遗憾,评测机非常古老,以至于你只能用古老的编程语言 Potato 来编写程序,关于 Potato 语言的语法详见下发的文档。
你需要提交一个 C++ 代码,这个 C++ 代码输出一份 Potato 代码来表示你这道题的答案。
在本题中,Potato 的变量 n 和 m 在一开始时会被设置成题目中的 n 和 m。
你需要按照题目要求求出这 m 个数,以任意顺序将它们放在 result[0⋯m−1] 中。
对于一组数据,有一个额外的限制 cell,我们会测量在这组数据上,有多少个 a 数组的元素在你的 Potato 代码运行过程中被修改了(一个元素被修改多次只算一次),把这个值记作 V。如果你没有正确计算出这 m 个数字或者 V>cell(试图修改了太多 a 数组的元素),则该组数据不通过,否则该组数据通过。
本题由 8 个 subtask 构成,每个 subtask 会评测 20 组数据,你的 C++ 代码将会得到一个输入 T 表示这是第几个 Subtask,你可以根据 T 输出不同的 Potato 代码。
对于前 7 个 subtask,如果你通过了这个 subtask 中至少 18 组数据,那么你可以获得这个 subtask 全部的分数,否则这个 subtask 你得 0 分。
对于第 8 个 subtask,如果你通过了少于 18 组数据,那么第 8 个 subtask 得 0 分,否则我们会根据这 20 组中你通过的数据中 V 的最大值计算出你这个 subtask 的分数。
另外,如果 20 组数据下来,你的 Potato 执行的总指令数超过了 2×108 条,或者你的 Potato 代码的行数超过了 10000 行,则你这个子任务得 0 分。
你可以使用我们下发的 Potato 模拟器(potato.cpp
)来测试你的程序,potato.cpp
的用法详见 potato-doc.pdf
。
你也可以用我们下发的 zip.cpp
来打包 Potato 程序,zip.cpp
会从 stdin
读入一个 Potato 代码,并从 stdout
输出这个 Potato 代码的 C++ 函数 output()。如果你的 Potato 代码过长,那么打包后的 output 函数代码长度可能超过 100KB 代码长度限制。
输入格式
第一行,一个正整数,表示是第几个子任务。
输出格式
输出你编写的 Potato 程序的代码。
子任务
- 子任务 1(5 分):m=1,cell=30。
- 子任务 2(10 分):m≤4,cell=1000。
- 子任务 3(5 分):1≤n≤100,cell=120。
- 子任务 4(5 分):保证所有数都出现了奇数次,cell=30。
- 子任务 5(15 分):1≤n≤1000,1≤m≤10,cell=30。
- 子任务 6(10 分):cell=1000。
- 子任务 7(10 分):cell=100。
- 子任务 8(40 分):按照使用的 cell 个数给分,具体来说,如果你通过的数据中使用的 cell 个数最多的为 x,那么你将得到 f(x) 分,其中 f(x) 如下描述:
f(x)={40x≤300x>100⌊3000−30x40+x⌋否则
对于所有数据,保证输入的数的范围都在 [0,232−1] 里,1≤n≤2.5×104,1≤m≤10。