题目描述

LIS 狐发现了小猪的房子。她没有像狼那样把房子吹倒，而是决定偷走小猪最珍贵的财产——也就是他拥有的最大数字。

小猪有一个长度为 n 的数组，其中存放着 0 到 n - 1 的一个排列。为了找出 n - 1 在哪里，LIS 狐可以要求小猪按某种指定方式重新排列数组，然后告诉她该新数组的最长上升子序列（LIS）的长度。

幸运的是，小猪并不是一只“有序的小猪”，因此保证初始数组是均匀随机生成的排列。

请帮助 LIS 狐找出：在最初的数组中，元素 n - 1 所在的位置。

长度为 k 的上升子序列，指的是一组下标 i_1 < i_2 < ... < i_k，并满足 a_{i_1} < a_{i_2} < ... < a_{i_k}。 最长上升子序列就是其中 k 最大的那一条。

任务要求

请编写程序 lis，实现函数 find_maximum。你的程序会与评测程序进行通信，并通过提出上述类型的问题来定位最大值在原数组中的位置。

在程序结束时，你必须返回原数组中最大值的位置。

实现细节

你需要实现如下函数：

int find_maximum(int n);

该函数会被评测程序调用 T 次，每次参数为整数 n。

为了与评测程序通信，你还可以调用下面的函数：

int get_lis_length(const std::vector<int>& p);

每次调用 get_lis_length 时，它会返回序列

$$a_{p_0}, a_{p_1}, ..., a_{p_{n-1}}$$

的最长上升子序列长度。

其中向量 p 必须是 0, 1, ..., n - 1 的一个排列。

函数 get_lis_length 的时间复杂度为 O(n log n)。

你的程序文件应命名为 lis.cpp，它可以包含你所需的其他代码和函数，但不能包含主函数 main。同时，你不能从标准输入读入，也不能向标准输出输出。

程序必须通过预处理指令包含头文件：

#include "lis.h"

限制

• 8 ≤ n ≤ 200
• 0 ≤ a_i ≤ n - 1
• a 是随机生成的排列；也就是说，对固定的 n，所有可能输入等概率出现
• T = 5 个测试

子任务

子任务	分值	N
1	5	= 8
2	35	= 20
3	60	= 200

某个子任务的分数只有在该子任务下的所有测试都通过时才能获得。

评分方式

• 设 q 为你的程序在单个子任务中调用 get_lis_length 的最大次数；
• 对于第一子任务，只要你在该子任务的所有测试中答案全部正确，就可以得到该子任务 100% 的分数；
• 对于第二、第三子任务，得分按如下方式计算：

$$\text{score}= \begin{cases} 1.0, & \text{如果 } q \le target \\ 0.9 \times \left(\frac{\log(target)}{\log(q)}\right)^{1.5}, & \text{否则} \end{cases}$$

其中

$$target= \begin{cases} 2 \cdot n^2, & \text{第二子任务} \\ 2 \cdot n, & \text{第三子任务} \end{cases}$$

示例交互

选手函数	评测程序
	find_maximum(3)
get_lis_length({0, 1, 2})	2
get_lis_length({0, 2, 1})
get_lis_length({2, 0, 1})	1
return(2)

说明：初始序列为 {1, 0, 2}。