loj#P2841. 「JOISC 2018 Day 4」图书馆
「JOISC 2018 Day 4」图书馆
题目描述
译自 JOISC 2018 Day4 T2「図書館 / Library」
在几百年之后,JOI 城已经变成了一片废墟,探索者 IOI 酱正在探索一片之前是图书馆的区域。根据探索得到的结果,她知道了下列事情:
- JOI 城的图书馆有 本书,它们从左向右放成一排;
- 这 本书编号为 到 。但是,书架上的书可能不按照编号顺序排列;
- 通过一次操作,可以一次性取出书架上一段连续的书。
不幸的是,IOI 酱找不到图书馆里的旧书了。但是她发现了一台能完成操作的机器。如果我们给机器传入了一些书(大于等于一本)的编号,它将会返回只取出给定编号的书需要的最小操作次数。
IOI 酱想要通过向机器传入编号以了解书架上书的顺序。然而,如果书的顺序是反的,机器的返回值将是一样的,因此她不需要确定书是从左向右放的还是从右向左放的。
因为这台机器太老了,她最多只能查询 次。
任务
写一个程序能够在最多查询 次的情况下确定书的顺序,不需要确定书从左向右放还是从右向左放。
输入格式
程序应该包含 library.h
头文件,你需要实现以下函数。
void Solve(int N)
对于每一个测试点,这个函数只调用一次,参数 N
是书架上书的数量。
你的程序可以调用以下函数:
-
int Query(const std::vector<int>& M)
-
如果至少 本书编号给定,这个函数将返回只取出这些书所用的最少次数。
-
从书架取出书的编号由长度为 的向量 决定。对于每个 ,如果
M[i-1]=0
,那么书 就不从书架取出,如果M[i-1]=1
,那么书 就从书架取出。如果 的大小不等于 ,你的程序将被判为Wrong Answer [1]
。对于每个 ,M[i-1]
应该为 或 。并且至少有一个为 。如果上述条件至少有一个不满足,你的程序将被判为Wrong Answer [2]
。如果函数Query
被调用超过 次,你的程序将被判为Wrong Answer [3]
。
-
-
void Answer(const std::vector<int>& res)
-
使用这个函数,你的程序应回答书架上书的顺序。不必确定书的摆放方向是从左至右还是从右至左。
-
参数
res
是一个长度为 的向量。它描述了书架上书的摆放顺序。对于每个 ,从左(或右)数第 本书的编号为res[i-1]
。如果res
的大小不等于 ,你的程序将被判为Wrong Answer [4]
。res[i-1]
应该是一个 到 的正整数(包括 和 )。如果条件不满足,你的程序将被判为Wrong Answer [5]
。所有整数res[0], res[1], ..., res[N-1]
应该两两不同。如果条件不满足,你的程序将被判为Wrong Answer [6]
。
-
当函数 Solve
停止运行时,如果 Answer
函数的调用次数不等于 ,你的程序将被判为 Wrong Answer [7]
。
如果 Solve
函数确定的书的顺序不同于书架上书的摆放顺序,你的程序将被判为 Wrong Answer [8]
。不必考虑书是从左至右放的还是从右至左放的。
重要提示
你的程序可以实现其他函数以供内部使用,或者使用全局变量。
你的程序不能使用标准输入输出,不能以任何方式与其他文件交互。但是,你的程序可以通过标准错误流输出调试信息。
数据范围与提示
对于全部数据,。
子任务
- (19 分) ;
- (81 分) 无特殊限制。