#1265. 【COMP350105期末实验】P1 带权中位数

说明

本系列题目为 2020 年为计算机试验班 91 开设的 COMP350105 “算法设计与分析” 课程之期末实验题目。 本题目的规定与要求不代表课程实验中的要求，本题目的得分不代表实验得分，本题目的数据也不代表课程期末实验的测试方式。 而且在本 OJ 上的程序正确性、效率性要求往往高于课程得分要求，但代码可读性、程序思想要求却低于课程得分要求。本题目为大家提供严谨的测试，请各位酌情根据自己能力解答。

题面原文

本题的约定

$w_i$ 为浮点数。带权中位数即满足上述条件的元素。

交互

为了严格控制该题的运行效率，本题采用交互方式进行。在开始交互之前，您的程序会得到序列的长度和第 $i$ 个元素的权值 $w_i$。交互的每一步，你的程序可以输出 q a b 询问两个元素 $x_a, x_b$，交互程序返回这两个元素的大小关系。

本题限制了交互时 q 询问的次数，如果您的程序询问次数超过 $n\times 5 + 10$，您的程序将被视为不通过。

在每次输出后，请刷新缓冲区，否则可能收到 idleness exceeded 错误，刷新缓冲区的方法如下：

fflush(stdout);       // c++
System.out.flush();   // java
stdout.flush()        # python
flush(output)         // pascal

每次测试进行一次交互，该组输入数据格式如下：

第一行一个整数 $n$，表示元素序列长度

第二行 $n$ 个由空格分开的浮点数，其中第 $i$ 个为 $w_i$

接下来，您的程序每进行一次 q 询问，输出一行一个整数 0 或 1，0 表示 $x_a \not < x_b$，1 表示 $x_a < x_b$。

在接受初始的交互数据后，您可以进行两种输出，请在输出后换行

• q a b，其中 $1 \leq a, b \leq n$ 为两个整数，表示需要询问的索引
• f，表示你的程序已经获得了答案，可以输出答案。此后不再允许询问

当你输出 f 后，以如下格式输出答案：

第一行一个整数 $k$，表示满足带权中位数条件的元素个数

第二行 $k$ 个由小到大整数，表示是带权中位数的元素下标

交互样例

5
0.1 0.5 0.2 0.1 0.1
q 1 2
1
q 2 3
0
q 4 5
1
r
2
2 5

样例解释

该样例按顺序展示了一种可能的交互，其中第三、五、七、九、十和十一行为用户输出，原序列为

3 7 5 4 6

交互程序以该依据返回比较结果，索引 2 5 表示两个带权中位数 7 6

$1 \leq n \leq 10^5$

$-10^9 \leq x_i \leq 10^9$，保证 $x_i$ 两两不同

$0 \leq w_i \leq 1$ 且 $w_i$ 的小数点后位数不超过 9

不保证有且仅有一个带权中位数

提示

您可以这样封装比较操作，query_lower 返回 $x_a < x_b$ 的真假

bool query_lower(int a, int b) {
    printf("q %d %d\n", a, b);
    fflush(stdout);
    int res;
    scanf("%d", &res);
    return res;
}

如果没有通过所有的测试点，请仔细检查数据范围