QOJ.ac

QOJ

Time Limit: 10 s Memory Limit: 256 MB Total points: 100

# 5361. 土豆评测机

统计

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

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

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

在本题中,Potato 的变量 $n$ 和 $m$ 在一开始时会被设置成题目中的 $n$ 和 $m$。

你需要按照题目要求求出这 $m$ 个数,以任意顺序将它们放在 $\mathtt{result}[0\cdots m-1]$ 中。

对于一组数据,有一个额外的限制 $\mathrm{cell}$,我们会测量在这组数据上,有多少个 $a$ 数组的元素在你的 Potato 代码运行过程中被修改了(一个元素被修改多次只算一次),把这个值记作 $V$。如果你没有正确计算出这 $m$ 个数字或者 $V > \mathrm{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 \times 10^8$ 条,或者你的 Potato 代码的行数超过了 $10\,000$ 行,则你这个子任务得 $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$,$\mathrm{cell} = 30$。
  • 子任务 2(10 分):$m \leq 4$,$\mathrm{cell} = 1\,000$。
  • 子任务 3(5 分):$1 \leq n \leq 100$,$\mathrm{cell} = 120$。
  • 子任务 4(5 分):保证所有数都出现了奇数次,$\mathrm{cell} = 30$。
  • 子任务 5(15 分):$1 \leq n \leq 1\,000$,$1 \leq m \leq 10$,$\mathrm{cell} = 30$。
  • 子任务 6(10 分):$\mathrm{cell} = 1\,000$。
  • 子任务 7(10 分):$\mathrm{cell} = 100$。
  • 子任务 8(40 分):按照使用的 $\mathrm{cell}$ 个数给分,具体来说,如果你通过的数据中使用的 $\mathrm{cell}$ 个数最多的为 $x$,那么你将得到 $f(x)$ 分,其中 $f(x)$ 如下描述:

$$ f(x) = \begin{cases}40 & x \leq 30 \\ 0 & x > 100 \\ \left\lfloor\frac{3000-30x}{40+x}\right\rfloor & \text{否则}\end{cases} $$

对于所有数据,保证输入的数的范围都在 $[0, 2^{32}-1]$ 里,$1 \leq n \leq 2.5 \times 10^4$,$1 \leq m \leq 10$。