题目描述
*题目描述可能与東方Project原设定不完全相符。
月之都正在阴谋向幻想乡迁移!
奇怪的机械已经在幻想乡中移动,并在「净化」幻想乡——他们在试图让幻想乡不再存在生物!灵梦不得不再次与早苗、魔理沙一同前去解决异变。
很快,她们便解决掉了在幻想乡前线的月兔清兰和铃瑚,并成功拿到了几台向月都发送情报时的加密工具。但是由于魔理沙一个魔炮轰上去把铃瑚一B带走了,所以这些加密工具也接近报废了。
经过河城荷取对窃听到的密文情报以及这台加密仪器的分析,她发现月都在前线发回的情报的加密方式其实比较简单。大约可以描述如下:
设月都发来的情报的字符集大小为n,则加密过程是将[1,n]中的n个整数一一对应到[1,n]的整数上。或者说,这个过程f(x)是一个[1,n]到[1,n]的双射。
而这些加密仪器,则可以在一次使用中对于任意给定的集合S,给出加密后的集合S′={x∣x=f(a),a∈S}。
但是根据河城荷取的分析,一台仪器最多再使用T次就会彻底报废。每台仪器所保有的加密方式以及T和n根据损坏情况与用途各不相同。
为了获取更多的计划情报,她们需要利用这些接近报废的加密仪器解出它们密文到原文的映射f′(x)。
由于这些仪器已经接近报废,她们需要尽快找到方法来解出解密所有月都情报的方法。
于是八云紫随手拉开一道隙间把你拉了出来,要你解决这个问题。如果不行就把你拉去隙间掉!
为了保命,你需要写一个程序完成所有几台仪器的处理。你的程序需要一次处理一台。
交互方式
你有两种交互方式:第一种是使用标准输入输出交互(Codeforces风格),第二种是使用函数调用来进行交互(WC/APIO/IOI风格)。
注意,我们提供的第二种交互方式的接口的底层实现是对第一种交互的简易封装。但是建议使用第二种来避免可能出现的InvalidInteraction错误。
标准I/O交互
首先你的程序可以从标准输入读取两个整数n和T,含义如题目描述所述。
你可以通过标准输出执行两种命令:
-
encode命令:用于进行一次加密操作。其后应跟随一个数字k表示加密集合的大小,后跟k个空格分隔的整数表示你要加密的集合。
例:encode3514495233表示对集合{233,495,514}进行加密。
该命令执行完毕后,你的程序可以在标准输入流中读取k个数,表示加密结果。
注意:你要尝试加密的集合不能带重。
-
submit命令:表示你已经得到了答案。其后应该有n个空格分隔的整数,第i个数表示i解密后的值。
你的程序在输出此命令后应当立即结束。
例:若n=3,你找到的解密方案是1→2,2→3,3→1,则你应当执行:submit231。
注意:如果你使用标准I/O进行交互,需要在输出命令后刷新stdout缓冲区(如std::flush、std::endl或fflush(stdout))。
函数调用交互
此部分仅支持C++语言。
首先需要包含头文件interaction.h。
你需要实现如下函数:
std::vector<int>Decode(intn,intT)
在每个测试点中,交互库会调用该函数恰好一次。
参数intn为题目描述中的n,intT为题目描述中的T。
函数返回值为包含密码表的std::vector<int>,其中下标为i的位置的值是i+1的解密结果。
交互库中可调用的函数:
std::vector<int> Encode(const std::vector<int>& v)
该函数返回v中值的加密结果。注意:加密集合不能带重。
数据范围与提示
本题共有20个测试点,各测试点的n(字符集大小)和T(最大查询次数)如下表:
| 测试点编号 |
n |
T |
测试点编号 |
n |
T |
| 1 |
0 |
11 |
1000 |
300 |
| 2 |
100 |
99999 |
12 |
100000 |
10000 |
| 3 |
1000 |
(未明确) |
13 |
20 |
6 |
| 4 |
100000 |
14 |
100 |
15 |
| 5 |
20 |
15 |
1000 |
40 |
| 6 |
100 |
75 |
16 |
100000 |
1020 |
| 7 |
1000 |
500 |
17 |
20 |
5 |
| 8 |
100000 |
50000 |
18 |
100 |
7 |
| 9 |
20 |
7 |
19 |
1000 |
10 |
| 10 |
100 |
35 |
20 |
100000 |
17 |
- 若程序未提交正确答案并正常结束,该测试点得0分。
- 若程序提交正确答案,但encode命令调用次数超过T,该测试点得0分;否则得满分。
- 注意:交互底层为标准I/O管道,总通信量过大可能导致超时。建议查询的∑∣S∣不超过1×107级别。