Public Judge

pjudge

Total points: 50 Output Only

# 21675. 【PER #3】DNA 匹配 2

Statistics

这是一道提交答案题。

在 P 宇宙中,生物的 DNA 是由一个 $0 \sim 2^{20}-1$ 内的整数表示的。DNA 由恰好 $20$ 个基因组成,对于一个用整数 $x$ 表示的 DNA,其包含第 $i$ ($1 \le i \le 20$) 个基因,当且仅当 $x$ 的二进制表示中从低到高第 $i$ 位为 $1$。

此外,据观察,任何两个不同的成年生物可以生出一个孩子,其 DNA 包含第 $i$ 个基因当且仅当两个成年人的 DNA 都包含该基因。

现在,你希望在 P 宇宙中生成 $2\,000$ 个成年生物,使得当这些生物两两生出一个孩子时,所有本质不同的孩子的数量尽可能多。我们认为两个孩子本质不同,当且仅当其 DNA 表示所对应的整数不同。

形式化的题意

构造 $2\,000$ 个在 $[0, 2^{20})$ 内的整数 $x_0,x_1,\cdots, x_{1999}$,使得集合 $V = \{x_i \operatorname{and} x_j \mid 0 \le i < j < 2000\}$ 的大小尽可能大。

输出格式

这是一道提交答案题,你只需要提交一个文件 1.out,描述你的构造。

输出只有一行,包含恰好 $2\,000$ 个在 $0 \sim 2^{20}-1$ 内的整数,表示你的构造。

在下发文件中,包含样例输出文件 sample.out,你可以利用此文件来参考正确的输出格式。

子任务

请注意,本题的满分为 50 分。

若你输出的方案不合法,则你的得分为 $0$。

否则,记 $X$ 表示你的构造中本质不同的孩子的数量(即形式化题意中集合 $V$ 的大小)。则你的得分为:

$X$ 的范围 $S$
$1\,000\,000 \le X$ $50$
$200\,000 \le X < 1\,000\,000$ $\frac{S - 200\,000}{1\,000\,000 - 200\,000} \times 50$
$X < 200\,000$ $0$

Hack

Hack 功能在本题中不可用。


or upload files one by one: