#1832. 排列

    ID: 1832 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1789来源:qoj.ac数据:公开样例构造

排列

排列

题目描述

标题: 排列 - Problem - QOJ.ac

Statistics

The problem was used in the following contests:

这是一道交互题。

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的内部。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

3
1 0 2
Correct.
cnt = 3