loj#P2841. 「JOISC 2018 Day 4」图书馆

「JOISC 2018 Day 4」图书馆

题目描述

译自 JOISC 2018 Day4 T2「図書館 / Library

在几百年之后,JOI 城已经变成了一片废墟,探索者 IOI 酱正在探索一片之前是图书馆的区域。根据探索得到的结果,她知道了下列事情:

  • JOI 城的图书馆有 NN 本书,它们从左向右放成一排;
  • NN 本书编号为 11NN。但是,书架上的书可能不按照编号顺序排列;
  • 通过一次操作,可以一次性取出书架上一段连续的书。

不幸的是,IOI 酱找不到图书馆里的旧书了。但是她发现了一台能完成操作的机器。如果我们给机器传入了一些书(大于等于一本)的编号,它将会返回只取出给定编号的书需要的最小操作次数。

IOI 酱想要通过向机器传入编号以了解书架上书的顺序。然而,如果书的顺序是反的,机器的返回值将是一样的,因此她不需要确定书是从左向右放的还是从右向左放的。

因为这台机器太老了,她最多只能查询 2000020000 次。

任务

写一个程序能够在最多查询 2000020000 次的情况下确定书的顺序,不需要确定书从左向右放还是从右向左放。

输入格式

程序应该包含 library.h 头文件,你需要实现以下函数。

void Solve(int N)

对于每一个测试点,这个函数只调用一次,参数 N 是书架上书的数量。

你的程序可以调用以下函数:

  • int Query(const std::vector<int>& M)

    • 如果至少 11 本书编号给定,这个函数将返回只取出这些书所用的最少次数。

    • 从书架取出书的编号由长度为 NN 的向量 MM 决定。对于每个 ii,如果 M[i-1]=0,那么书 ii 就不从书架取出,如果 M[i-1]=1,那么书 ii 就从书架取出。如果 MM 的大小不等于 NN,你的程序将被判为 Wrong Answer [1]。对于每个 iiM[i-1] 应该为 0011。并且至少有一个为 11。如果上述条件至少有一个不满足,你的程序将被判为 Wrong Answer [2]。如果函数 Query 被调用超过 2000020000 次,你的程序将被判为 Wrong Answer [3]

  • void Answer(const std::vector<int>& res)

    • 使用这个函数,你的程序应回答书架上书的顺序。不必确定书的摆放方向是从左至右还是从右至左。

    • 参数 res 是一个长度为 NN 的向量。它描述了书架上书的摆放顺序。对于每个 ii,从左(或右)数第 ii 本书的编号为 res[i-1]。如果 res 的大小不等于 NN,你的程序将被判为 Wrong Answer [4]res[i-1] 应该是一个 11NN 的正整数(包括 11NN)。如果条件不满足,你的程序将被判为 Wrong Answer [5]。所有整数 res[0], res[1], ..., res[N-1] 应该两两不同。如果条件不满足,你的程序将被判为 Wrong Answer [6]

当函数 Solve 停止运行时,如果 Answer 函数的调用次数不等于 11,你的程序将被判为 Wrong Answer [7]

如果 Solve 函数确定的书的顺序不同于书架上书的摆放顺序,你的程序将被判为 Wrong Answer [8]。不必考虑书是从左至右放的还是从右至左放的。

重要提示

你的程序可以实现其他函数以供内部使用,或者使用全局变量。

你的程序不能使用标准输入输出,不能以任何方式与其他文件交互。但是,你的程序可以通过标准错误流输出调试信息。

数据范围与提示

对于全部数据,1N1000,1AiN,AiAj1\le N\le 1000,1\le A_i\le N,A_i\neq A_j

子任务

  1. (19 分) N200N\le 200
  2. (81 分) 无特殊限制。