loj#P3172. 「IOI2017」大奖

「IOI2017」大奖

题目描述

很抱歉,由于技术局限,本题只支持各版本 C++

提示:请参考选手目录下的示例代码,int[] 的实际实现方式为 std::vector<int>

「大奖」是一个家喻户晓的 TV 游戏节目。这次你很幸运地进入到最后一轮。已知编号从 00n1n-1nn 个盒子从左到右排成一行,你就站在这排盒子的前面。每个盒子里面放有一个奖品,必须打开盒子才能看到是什么奖品。已知有 v2v \ge 2 种不同类型的奖品。这 vv 种类型按照奖品价值的降序从 11vv 排列。

类型 11 的奖品是一块钻石,价值最高。所有盒子加起来刚好只有一块钻石。类型 vv 的奖品是一块棒棒糖,价值最低。为使得游戏更加激动人心,相对便宜的奖品数量远比价值昂贵的奖品数量要多。更具体一点,对于满足 2tv2 \le t \le v 的所有 tt,我们有:如果类型 t1t-1 的奖品有 kk 个,那么类型 tt 的奖品将严格多于 k2k^2 个。

你的目标是赢得那块钻石。在游戏结束时,你必须打开一个盒子并收取盒子内的奖品。在选择要打开的盒子之前,你可以向节目主持人 Rambod 提一些问题。在每一个问题中,你选择就某个 ii 号盒子进行提问。Rambod 将给你一个包含两个整数的数组 aa 作为回答。这两个整数的意义如下:

  • ii 号盒子左面的盒子中,刚好有 a[0]a[0] 个盒子中的奖品,价值比 ii 号盒子中的奖品价值要高。
  • ii 号盒子右面的盒子中,刚好有 a[1]a[1] 个盒子中的奖品,价值比 ii 号盒子中的奖品价值要高。

例如,假设 n=8n=8,在你的问题中,你选择就 22 号盒子进行提问。Rambod 的回答是 a=[1,2]a=[1, 2]。这个回答的意义是:

  • 00 号盒子和 11 号盒子中恰好有一个盒子中的奖品比 22 号盒子中的奖品更贵。
  • 3,4,,73,4,\ldots,7 号盒子中恰好有 22 个盒子中的奖品比 22 号盒子中的奖品更贵。

你的任务就是通过问少量的问题找出包含钻石的盒子。

实现细节

你应当实现如下函数段:

int find_best(int n)
  • 此函数只被评测程序调用仅一次。
  • nn:盒子的数量.
  • 你实现的这个函数应该返回装有钻石的盒子编号,即,唯一的整数 d (0dn1)d~(0 \le d \le n-1) 使得 dd 号盒子放有类型为 11 的奖品。

上述函数可以调用下列函数:

int[] ask(int i)
  • ii:你在询问时选择的盒子编号。ii 的数值必须介于 00n1n-1 之间(含)。
  • 这个函数返回包含 22 个元素的数组 aa。其中,a[0]a[0] 是在 ii 号盒子的左面,奖品比 ii 号盒子的奖品价值更高的盒子数目。而 a[1]a[1] 则是在 ii 号盒子右面,奖品比 ii 号盒子的奖品价值更高的盒子数目。

例子

评测工具将做如下函数调用:

find_best(8)

这里有 n=8n=8 个盒子。假定奖品类型为 [3,2,3,1,3,3,2,3][3, 2, 3, 1, 3, 3, 2, 3]。对函数 ask 的所有可能的调用以及相应的返回值列出如下:

  • ask(0) 返回 [0,3][0, 3]
  • ask(1) 返回 [0,1][0, 1]
  • ask(2) 返回 [1,2][1, 2]
  • ask(3) 返回 [0,0][0, 0]
  • ask(4) 返回 [2,1][2, 1]
  • ask(5) 返回 [2,1][2, 1]
  • ask(6) 返回 [1,0][1, 0]
  • ask(7) 返回 [3,0][3, 0]

在这个例子中, 钻石放在 33 号盒子里。所以函数 find_best 应该返回 33

IOI2017-prize-desc.png

上图阐释了这个例子。图中上半部分给出了每个盒子中奖品的类型。图中的下半部分阐释了询问 ask(2)。做了标记(打\surd)的盒子中装有比 22 号盒子的奖品价值更高的奖品。

限制

  • 3n2000003 \le n \le 200000
  • 每个盒子中奖品的类型介于 11vv 之间(含).
  • 类型 11 的奖品恰有一个。
  • 对于所有 2tv2 \le t \le v,如果类型 t1t-1 的奖品有 kk 个,那么类型 tt 的奖品将严格多于 k2k^2 个。

子任务与评分

在某些测试数据中,评测工具的行为是自适应的。这意味着在这些测试数据中评测工具并没有一个固定的奖品序列。取而代之的是,由评测工具给出的答案可能依赖于你的程序问过的问题。评测工具的回答方式可以保证,在每次回答之后,至少有一个奖品序列与到目前为止给出的所有回答都不冲突。

1.(2020 分)恰好有 11 个钻石和 n1n-1 个棒棒糖(所以,v=2v=2)。你可以调用函数 ask 最多 1000010000 次。

2.(8080 分)没有附加限制。

在子任务 22 中你可以获得部分分。令 qq 是在这个子任务的所有测试数据上函数 ask 被调用的最大次数,那么你在这个子任务上的得分将按照下表计算:

问题 得分
10000<q10000<q 00 (Wrong Answer)
6000<q100006000<q\le10000 7070
5000<q60005000<q\le6000 80(q5000)/10080-(q-5000)/100
q5000q\le5000 8080

评测工具示例

评测工具的这个示例不是自适应的。取而代之的是,它只是读取并使用一个固定的奖品类型的数组 pp。对于所有的 0bn10 \le b \le n-1bb 号盒子中的奖品类型将由 p[b]p[b] 给出。评测工具示例期望的输入格式如下:

  • 11 行:nn
  • 22 行:p[0] p[1]  p[n1]p[0]~p[1]~\cdots~p[n-1]

评测工具示例输出单独一行,其中包含 find_best 的返回值以及调用函数 ask 的次数。