QOJ.ac

QOJ

Time Limit: 10 s Memory Limit: 256 MB Total points: 100
[0]

# 5361. 土豆评测机

Statistics

有一个很简单的问题,你有 n 个数,其中 m 个数值出现了奇数次,剩下的数值都出现了偶数次,请你找出这 m 个数。

很遗憾,评测机非常古老,以至于你只能用古老的编程语言 Potato 来编写程序,关于 Potato 语言的语法详见下发的文档。

你需要提交一个 C++ 代码,这个 C++ 代码输出一份 Potato 代码来表示你这道题的答案。

在本题中,Potato 的变量 nm 在一开始时会被设置成题目中的 nm

你需要按照题目要求求出这 m 个数,以任意顺序将它们放在 result[0m1] 中。

对于一组数据,有一个额外的限制 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=1cell=30
  • 子任务 2(10 分):m4cell=1000
  • 子任务 3(5 分):1n100cell=120
  • 子任务 4(5 分):保证所有数都出现了奇数次,cell=30
  • 子任务 5(15 分):1n10001m10cell=30
  • 子任务 6(10 分):cell=1000
  • 子任务 7(10 分):cell=100
  • 子任务 8(40 分):按照使用的 cell 个数给分,具体来说,如果你通过的数据中使用的 cell 个数最多的为 x,那么你将得到 f(x) 分,其中 f(x) 如下描述:

f(x)={40x300x>100300030x40+x否则

对于所有数据,保证输入的数的范围都在 [0,2321] 里,1n2.5×1041m10