时间限制： 1s
空间限制： 256MB

题目类型说明

这是一道提交函数题 / 交互式思维题 / 评分题。

你不需要编写 main 函数，而是需要实现指定函数。系统中存在一个长度为 N 的隐藏 01 串，你可以通过若干次查询来获取信息，并最终返回其中某一段最长连续 1 子段的位置。

题目描述

存在一个隐藏的长度为 N 的比特数组：a_0, a_1, ..., a_{N-1}。

一次查询中，你可以选择若干个位置并翻转这些位置上的比特：

• 0 会变成 1；
• 1 会变成 0。

每次查询之后，评测程序会告诉你：当前数组中最长连续全 1 子数组的长度。

注意，这些翻转是持续生效的。也就是说，前一次查询中被翻转的比特，会一直保持翻转后的状态，直到之后再次被翻转回来。

你的目标是：在完成若干次查询后，找出隐藏数组中某一段最长连续全 1 子数组的位置。如果存在多段同样长的最优答案，返回任意一段即可。

要求使用尽可能少的查询次数。

你需要实现的函数

std::pair<int,int> find_longest_subarray_of_ones(int n);

该函数会在每个子测试中被调用一次，参数 n 表示隐藏数组长度。

你需要返回一对整数 {l, r}，表示某个最长连续全 1 子数组的左右端点，其中：

• l 为左端点下标；
• r 为右端点下标。

你可以调用的查询函数

int flip_bits(const std::vector<bool> &flips);

其中 flips 是一个长度为 N 的比特向量：

• flips_i = 1 表示需要翻转 a_i；
• flips_i = 0 表示不翻转 a_i。

在执行这些翻转后，函数会返回当前隐藏序列中最长连续全 1 子数组的长度。

提交要求

你需要提交文件 ones.cpp，其中必须包含：

• find_longest_subarray_of_ones 函数；
• 你自己编写的其他辅助函数或代码。

但不能包含：

• main 函数；
• 任何从标准输入读取数据的代码；
• 任何向标准输出打印内容的代码。

你的程序还必须包含头文件：

#include "ones.h"

本地测试

题目提供了本地评测器 Lgrader.cpp，可与你的程序一起编译测试。

本地评测器输入格式如下：

• 第一行是整数 T，表示本测试中共有多少个子测试；
• 对于每个子测试：
  • 第一行给出整数 N；
  • 第二行给出隐藏数组 a_0 ... a_{N-1}。

如果你的程序运行正确，本地评测器会输出两项信息：

• 1
• 你的程序在所有子测试中使用的最大查询次数。

否则会输出 0。

样例交互说明

假设初始数组为 1,0,1，则一种可能的交互过程如下：

选手程序	评测程序
调用 find_longest_subarray_of_ones(3)
调用 flip_bits({0,0,0})	返回 1
调用 flip_bits({0,1,0})	返回 3
返回 {0,2}

数据范围

• T = 5
• 1 <= N <= 10^4
• 0 <= a_i <= 1

评分方式

如果你的程序在任意一个子测试中出错，则本题得分为 0。

否则，设你的程序在单个子测试中使用的最大查询次数为 Q，则得分为：

当 Q >= 60 时：

$$\left(\frac{60}{Q}\right)^{0.215} \times 70$$

当 Q < 60 时：

$$-\frac{3}{2}\max(40,Q)+160$$

也就是说，查询次数越少，得分越高。