这是一道交互题。
在 AutoLab 平台上有一台奇怪的 $k$ 位计算机,其中 $k$ 是一个固定的常数 $8192 = 2^{13}$。这台计算机的字长恰好为 $\frac{k}{8} = 1024 = 2^{10}$,且其存储整数的方式如下:
每个整数会存储在连续的 $k$ 个 bit 中。假设将这 $k$ 个连续 bit 的值按照下标从小到大顺次排列后得到的长度为 $k$ 的 01 字符串为 $S$ 。假设 $S$ 的下标从 $0$ 开始,则这个字符串 $S$ 对应的整数值为 $f(S) = \sum \limits_{i=0}^{k-1} [S_i==1] sgn_i 2^i$, 其中 $sgn$ 是一个小 W 预先定义的长度为 $k$ 的数组,其下标从 $0$ 开始且 $\forall 0 \le i < k,sgn_i \in \{-1,1\}$。出于某些特殊的原因,这台计算机上保证了 $sgn_{k-1} = 1,sgn_{k-2} = -1$。而你不知道 $sgn_0,sgn_1,\cdots,sgn_{k-3}$ 的值。
假设 $L = \sum \limits_{i=0}^{k-1} \min\{0,sgn_i\} 2^i$,$R = \sum \limits_{i=0}^{k-1} \max\{0,sgn_i\} 2^i$, 则发现 $\forall L \le x \le R$,恰好有一个长度为 $k$ 的 01 字符串 $f(T)$, 使得 $f(T) = x$(证明略去)。不妨设所有 $[L,R]$ 内的整数构成的集合为 $S$,则 $f$ 是一个从 $\{0,1\}^n$ 到 $S$ 的双射。据此我们可以设 $f(x)$ 的反函数 $g(x)$ 存在,且其满足 $\forall x \in S,f(g(x)) = x$。
假设存在 $x,y \in S$ ,则在该计算机上两个整数之间的加法 $\oplus$ 被定义为 $x \oplus y \overset{def}{=} (x + y - L + 2^k) \bmod 2^k + L$。不难发现 $\forall x,y \in S,x \oplus y \in S$。因而在这台计算机上加法满足封闭性。同时按照如上规则定义的加法也满足交换律,结合律等性质。这些性质的证明也同样略去。
学生可以通过有限次的询问获得和 $sgn_i$ 相关的信息。每次询问你可以给计算机两个长度为 $k$ 的仅包含 0,1 的字符串 $x,y$,而计算机会返回 $g(f(x) \oplus f(y))$ 的值。本次的作业要求是在不超过 $m$ 次的询问中求出$sgn_0,sgn_1,\cdots,sgn_{k-3}$ 的准确值。
小 Z 是一名聪明绝顶的学生,因而他尝试使用他的 $10^3 \mathrm{Hz}$ 的超强大脑来手算出每次交互的值。但是他发现给他的处理速度还是跟不上庞大的数据规模。因而它请你帮忙写一个程序,帮助他更快速的完成本次的作业。
任务
本题仅支持 C++。
你需要包含头文件 datalab.h
。
你不需要,也不应该实现主函数,你只需要实现如下一个函数:
std::vector<int> solve(int k,int m)
:- 传入数字的是计算机的字长 $k$ 和询问次数限制 $\mathrm{m}$。
- 你需要返回一个大小为 $k$ 的
vector
,其第 $i$ 个元素代表你确定的 $sgn_i$ 的值。
你可以通过如下函数调用 Autolab 上的加法操作。
std::bitset<8192> Add(std::bitset<8192> x,std::bitset<8192> y)
:- 给定两个大小为 $k$ 的 bitset, 每个 bitset 自低位向高位阅读的结果代表了一个长度为 $k$ 的仅包含 01 的字符串。
- 返回一个大小为 $k$ 的 bitset, 表示 $g(f(x) \oplus f(y))$ 的值。返回的格式和输入的格式相同。
根据题目要求,你至多只能询问 $\mathrm{m}$ 次两个整数在这台计算机上的加法结果。也就是说你至多只能调用 $\mathrm{m}$ 次 Add
函数。
评测时,交互库会恰好调用 solve
一次。
本题保证所使用的数组 sgn
在开始之前已经完全确定,不会根据和你的程序的交互过程动态构造,因此题目中的交互操作都是确定性的,你不需要关心这些操作在交互库中的具体实现。
数据保证在调用次数限制下,交互库运行所需的时间不超过 1s;交互库使用的内存大小固定,且不超过 128MB。
如何测试你的程序
试题目录下的 grader.cpp
是我们提供的交互库参考实现,最终测试时所用的交互库实现与该参考实现有所不同,因此选手的解法不应该依赖交互库实现。
- 你需要在本题目录下使用如下命令编译得到可执行程序:
g++ grader.cpp sample.cpp -o sample -O2 -lm
- 对于编译得到的可执行程序:
- 可执行文件将从标准输入读入以下格式的数据:
- 第一行包含两个整数 $k,\mathrm{m}$。
- 接下来一行 $k$ 个整数,第 $i$ 个数字表示 $sgn_i$。
- 读入完成之后,交互库将调用恰好一次函数 $\texttt{solve}$ 你的函数正确返回后,交互库会判断你的计算是否正确,若正确则会输出
Correct
和交互函数调用次数相关信息,否则会输出相应的错误信息。
- 可执行文件将从标准输入读入以下格式的数据:
试题目录下有出题人提供的一份参考代码 sample.cpp
,注意这份代码 不保证可以通过所有的测试用例 。
样例数据
样例 1
见下发文件。
样例 2
见下发文件。
这两个样例满足可执行程序的输入格式,因而可以直接输入到可执行程序中。
数据范围
子任务 | $k$ | $m$ |
---|---|---|
1 | $= 8192 = 2^{13}$ | $= 8200$ |
2 | $= 5550$ | |
3 | $= 4096 = 2^{12}$ |
评分方式
对于任意一个子任务中的数据,如果在某一个数据上选手返回了错误的答案,或者是超出了询问次数限制,得分为 $0$。
否则假设在子任务内所有测试点中,询问次数的最大值为 $a$,则对于每个子任务,选手得分为:
- Subtask $1$: $10$
- Subtask $2$: $15$
- Subtask $3$: $\min \{75, \frac{13800}{\max\{a,1\}} \}$
换而言之,当且仅当 $a \le 184$ 的时候,Subtask $3$ 可以获得满分。
选手在本题为本题三个子任务的得分之和。