这是一道交互题。
Alice和Bob在玩猜数游戏。首先,Alice选择b∈{0,1},Bob不知道b的值。随后Alice按照如下方式生成一个{0,1}64上的排列。
- 若b=0,则P从{0,1}64上的所有排列中均匀随机抽取;
- 若b=1:
- f1,f2,f3分别从{0,1}32→{0,1}32的所有函数中独立均匀随机抽取
- 为了计算P(x),Alice首先将x拆分为x=x0∘x1,x0,x1各长32bit
- Alice进行如下的计算:
- x2=x0⊕f1(x1)
- x3=x1⊕f2(x2)
- x4=x2⊕f3(x3)
- Alice将x3∘x4作为P(x)的输出。换言之,P(x0∘x1)=x3∘x4,其中x3,x4的定义方式如上
不难看出对于两种情况,得到的P都是一个良定义的排列。现在Bob需要确定b的值。他可以向Alice进行如下两种询问:
- Bob任取x∈{0,1}64,并询问P(x)
- Bob任取x∈{0,1}64,并询问P−1(x)
由于Alice还要去赶DDL,她要求Bob只能进行不超过256次询问。然而Bob并不擅长应对随机化的问题,于是他来向你寻求帮助。请帮Bob设计一个算法来正确猜测b。
交互方式
本题仅支持c++
。你应当在你提交的源文件中包含interaction.h
(见下发文件)。交互所使用的接口函数定义如下:
/**
* @brief Queries P(x) or P^{-1}(x)
* @param x The value to query
* @param rev Set rev=0 to query P(x), rev=1 to query P^{-1}(x)
* @return P(x) for rev=0, P^{-1}(x) for rev=1
*/
unsigned long long getperm(unsigned long long x,int rev);
/**
* @brief Make no more than 256 calls to getperm, to guess b
* @see getperm
* @return The b you guesses
*/
int guessb();
你应当在你的源文件中实现int guessb()
。它应当通过调用getperm
来进行不超过256次询问,并返回0/1作为其对b的猜测。如果有不清楚的地方,下发文件中的permutation.cpp
是一个简易实现,你可以在其基础上进行修改得到你的源文件。
编译&运行
使用
g++ -o grader grader.cpp permutation.cpp
来将你的源文件和交互库一起编译,并得到可执行文件grader
。其中permutation.cpp
是你本地的源文件名。
随后对于Linux/MacOS,使用
./grader
来运行;对于Windows,使用
grader.exe
来运行。
输入
每一个测试点包含多组数据
第一行包含一个正整数t,表示数据的组数
第二行包含两个64位无符号整数s0,s1(0≤s0,s1≤264−1),代表grader
所使用的随机数种子
这是grader.cpp
的工作。你不应当在提交的源文件中从标准输入读取任何数据。
输出
对于每组数据输出一行。若调用了超过256次询问,则输出QLE
。否则若对于b的猜测结果正确,则输出OK
;若猜测错误,则输出WA
。
这是grader.cpp
的工作。你不应当在提交的源文件中向标准输出写入任何数据。
数据范围及约定
对于20%的测试点,t=1
对于另外20%的测试点,t=4
对于剩下60%的测试点,t=100
我们保证OJ上grader.cpp
处理25600次询问所需总时间不超过10ms
关于用整数表示二进制字符串:我们约定整数的最低位对应第一个二进制字符,最高位对应最后一个二进制字符。因此,对于x=x0∘x1,x0是x的低32位,而x1是x的高32位。例如,对于x=0xFEDCBA9876543210
,我们有x_0=0x76543210
以及x_1=0xFEDCBA98
。对于x3∘x4同理。
注意事项
下发的grader.cpp
仅供参考。在OJ上评测时,我们会使用不同的grader.cpp
(保证接口的功能相同)。你提交的源文件只能访问interaction.h
中提供的接口,而不应当试图访问grader.cpp
的内部。