题目描述

给定 $N$ 个隐藏的、非空的开区间 $(L_i, R_i)_{i=0,\ldots,N-1}$。你的任务是找出其中一个规模最大的区间集合，使得这些区间具有非零长度的公共交集。

为了做到这一点，你可以发出查询，查询会返回某个给定区间集合的交集长度。然后你需要返回一个区间下标集合，使得存在某个实数同时属于这些区间中的每一个。请在使用尽可能少的查询次数的前提下完成任务。

数据范围

• $1 \le N \le 5000$
• $1 \le L_i < R_i \le 10^9$

交互说明

这是一个交互题。你需要编写如下函数，它会被调用一次，参数为区间个数；函数应返回一个由互不相同的下标组成的向量，下标范围为 $0$ 到 $N-1$：

vector<int> max_cardinality_intersection(int n);

你可以通过下面提供的查询函数，获得指定若干区间交集的长度。该函数的时间复杂度与传入下标个数成线性关系。要求 indices.size() >= 1。

int length_intersection(vector<int> indices);

你的代码中不应包含 main 函数，但可以包含任意其他辅助函数、类、变量等。

为便于本地测试，题目提供了本地 grader 和接口头文件副本。测试时，你应将自己的代码与本地 grader 一起编译。把它们放在同一目录下后，可使用如下命令：

g++ -O2 -std=c++17 -Wall intervals.cpp Lgrader.cpp -o intervals.exe

子任务

子任务	分值	$N \le$
1	9	10
2	61	100
3	30	5000

评分方式

设 $Q$ 为你在某个子任务的某个测试中提出的问题数的最大值，设 $A(MAXN)$ 为该子任务中作者解法所使用的查询次数。

1. 如果你发出了非法查询，或者未能找出最大数量的区间，则该测试得分为 $0$。
2. 在第一个子任务中，只要答案正确，就能获得该子任务的 $100\%$ 分数。
3. 否则，按下式获得该子任务的部分分：

$$\text{points}= \begin{cases} \dfrac{1}{\sqrt{\log_2\left(1+\dfrac{Q}{A(MAXN)}\right)}}, & \text{如果 } Q>A(MAXN),\\ 1.0, & \text{否则。} \end{cases}$$

样例交互

当 $N=3$，隐藏区间分别为 $(1,5)$、$(5,8)$ 和 $(2,6)$ 时，一组可能的交互如下：

选手	评测系统
	max_cardinality_intersection(3)
length_intersection({0})	4
length_intersection({1, 2})	1
length_intersection({0, 1})	0
return {1,2}