QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 256 MB Total points: 100 Interactive
[0]

# 8955. 排列

Statistics

这是一道交互题。

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=x0x1x0,x1各长32bit
    • Alice进行如下的计算:
      • x2=x0f1(x1)
      • x3=x1f2(x2)
      • x4=x2f3(x3)
    • Alice将x3x4作为P(x)的输出。换言之,P(x0x1)=x3x4,其中x3,x4的定义方式如上

不难看出对于两种情况,得到的P都是一个良定义的排列。现在Bob需要确定b的值。他可以向Alice进行如下两种询问:

  • Bob任取x{0,1}64,并询问P(x)
  • Bob任取x{0,1}64,并询问P1(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,s10s0,s12641),代表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=x0x1x0x的低32位,而x1x的高32位。例如,对于x=0xFEDCBA9876543210,我们有x_0=0x76543210以及x_1=0xFEDCBA98。对于x3x4同理。

注意事项

下发的grader.cpp仅供参考。在OJ上评测时,我们会使用不同的grader.cpp(保证接口的功能相同)。你提交的源文件只能访问interaction.h中提供的接口,而不应当试图访问grader.cpp的内部。