当前没有测试数据。

寻找位置（find）

TOI-22 practice Tasks · English (ISC)
时间限制：1 秒　内存限制：512 MB

题目描述

给定 (N) 个整数 (A_0,A_1,\ldots,A_{N-1})。题目保证这些数按从大到小的顺序排列，并写明：

[ A_i\ge A_{i+1}\qquad(0\le i<N-2) ]

我们要找到最小的下标 (p)，使 (A_p=K)。如果不存在符合条件的 (p)，答案为 (-1)。

在本题中，你不能直接得知任何 (A_i) 的值，但可以查询指定位置的 (A_i) 是小于、大于还是等于 (K)。你需要尽量减少查询次数；每组测试数据的得分取决于查询次数。

编程要求

实现以下函数：

int find(int N);

• N：整数的个数。
• 返回值：满足 (A_p=K) 的最小下标 (p)；如果不存在，则返回 -1。

A 和 K 都不是 find 的输入参数。选手的程序不能直接访问它们，只能通过以下函数查询 (A_i) 与 (K) 的关系：

int look(int i)

look(i) 的返回值为：

计分方式

设一次 find 调用中，look 共被调用 (q) 次：

示例 1

设 (N=7)，(A=[10,8,5,5,3,3,1])，(K=3)，考虑调用 find(7)。

假设程序从左到右查询：

程序确定值等于 (K) 的最小下标是 4，因此返回 4，答案正确。但它调用了 5 次 look，而 (\lceil\log_2 7\rceil+1=4<5)，所以这组数据只获得 30% 的分数。

示例 2

(N)、(A)、(K) 与示例 1 相同。假设查询顺序为：

1. look(3) 返回 1，因为 (A_3>3)。
2. look(5) 返回 0，因为 (A_5=3)。虽然找到了等于 (K) 的元素，但还不能停止，因为更小的下标也可能满足条件。
3. look(4) 返回 0，因为 (A_4=3)。

此时程序确定最小下标为 4，返回 4。它只调用了 3 次 look，不超过 (\lceil\log_2 7\rceil+1=4)，因此获得这组数据 100% 的分数。

数据范围与子任务

[ 1\le N\le1{,}000{,}000 ]

样例评测器

样例评测器按以下格式读取数据：

• 第 1 行：(N) 和 (K)。
• 第 2 行：(A_0,A_1,\ldots,A_{N-1})。

之后，评测器调用选手的 find 函数，在屏幕上输出函数的返回值，随后输出 look 的调用次数。