QOJ.ac

QOJ

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

#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$。

About Issues

We understand that our problem archive is not perfect. If you find any issues with the problem, including the statement, scoring configuration, time/memory limits, test cases, etc.

You may use this form to submit an issue regarding the problem. A problem moderator will review your issue and proceed it properly.

STOP! Before you submit an issue, please READ the following guidelines:

  1. This is not a place to publish a discussion, editorial, or requests to debug your code. Your issue will only be visible by you and problem moderators. Other users will not be able to view or reply your issues.
  2. Do not submit duplicated issues. If you have already submitted one, please wait for an moderator to review it. Submitting multiple issues will not speed up the review process and might cause your account to be banned.
  3. Issues must be filed in English or Chinese only.
  4. Be sure your issue is related to this problem. If you need to submit an issue regarding another problem, contest, category, etc., you should submit it to the corresponding page.

Active Issues 0

No issues in this category.

Closed/Resolved Issues 0

No issues in this category.