注意事项

在 LibreOJ 上，由于语言限制，目前只支持以下语言的提交：

• C++（标准为 C++ 17 及以上）

请在提交源代码前添加 #include "hora.h"。

题目描述

题目译自 eJOI2024 Day2 T3. Hora

这是一个交互题 。

霍拉舞（Hora）是一种传统的罗马尼亚和摩尔多瓦的民间舞蹈，参与者手拉手形成一个大圈……

在第八届欧洲青少年信息学奥林匹克比赛上，有 $N$ 名参与者开始跳霍拉舞，其中 $N$ 是一个正偶数。男孩和女孩的数量相等。组织者为霍拉舞中的每个参与者分配了一个环形编号。编号从 $0$ 开始，按顺序依次递增 $1$，直到 $N-1$。这意味着编号为 $0$ 和 $N-1$ 的参与者是邻居，并且每个参与者的编号比其前一个邻居的编号大一。

你不知道哪些参与者是女孩，哪些参与者是男孩，因为你现在正在参加比赛！不过，你可以发起若干次询问。每次询问包含两个整数 $L$ 和 $R$，满足 $0 \leq L<N$ 和 $0 \leq R<N$。交互器将会给出一个整数，表示环上从 $L$ 到 $R$ 的连续区间中的男孩数量。具体来说：

• 如果 $L \leq R$，表示环上编号为 $L, L+1, \ldots, R-1, R$ 的参与者的连续区间。
• 如果 $R<L$，表示环上编号为 $L, L+1 \ldots N-1,0 \ldots R-1, R$ 的参与者的连续区间。

你给定了一个整数 $K$ $(1 \leq K \leq N)$。你的任务是在环上找到一个长度为 $K$ 的连续区间，使得该区间内男孩和女孩的数量差的绝对值最小。更正式地说，你需要实现一个函数，返回一个整数 $S$ $(0 \leq S<N)$，使得从 $S$ 开始的长度为 $K$ 的连续区间在环上所有长度为 $K$ 的连续区间中，男孩和女孩数量差的绝对值最小。请注意，某些环可能有多个具有相同最小数量差的绝对值的 $S$。在这种情况下，你可以返回其中任何一个。

两个数 $x$ 和 $y$ 之间的差的绝对值为 $|x-y|$。例如，$|2-4|=2$，$|7-4|=3$。

评分程序不是自适应的，即环上的每个参与者性别在开始之前便已经确定了。

实现细节

你需要实现以下函数：

int solve(int N, int K)

• $N$：霍拉舞参与者的数量。
• $K$：考虑的区间的长度。
• 该函数应返回 $S$，表示开始长度为 $K$ 的区间的整数，且该区间内男孩和女孩数量差的绝对值最小。
• 该函数只被调用一次。

上述函数可以调用以下函数：

int ask(int L, int R)

• $L$ ：查询区间的开始编号。
• $R$ ：查询区间的结束编号。
• 返回查询区间内的男孩数量。
• 如果对 ask 函数的调用次数超过 $10^5$ 次，代码将会被判为 Wrong Answer。

样例

假设圈子如下图所示：

请注意，带有白色字母 B 的圆圈代表男孩，带有黑色字母 G 的圆圈代表女孩。此外，每个圆圈右侧的数字表示相应人的编号。

考虑以下调用：

solve(12, 5)

在这个样例中，我们有 $12$ 个人跳霍拉舞，我们搜索长度为 $5$ 的连续区间，且男孩和女孩数量差的绝对值最小。

程序发起调用：

ask(0, 10)

对应的答案是 $6$，意味着在这个区间中有 $6$ 个男孩跳霍拉舞。我们可以很容易地推断出同一区间内有 $5$ 个女孩跳霍拉舞。

ask(0, 4)

对应的答案是 $4$，意味着在这个区间中有 $4$ 个男孩跳霍拉舞。

ask(1, 5)

对应的答案是 $3$，意味着在这个区间中有 $3$ 个男孩跳霍拉舞。我们可以很容易地推断出同一区间内有 $2$ 个女孩跳霍拉舞。由于 $3$ 和 $2$ 之间的差的绝对值为 $1$，且不存在更小数量差的绝对值的长度为 $5$ 的区间，因此程序返回 $1$，这是对应区间的起始位置。

数据范围与提示

对于所有输入数据，满足：

• $2 \leq N \leq 10^5$
• $1 \leq K \leq N$
• $N$ 是偶数。
• 霍拉舞中男孩和女孩的数量相等。

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制	$Q_{full}$
$1$	$5$	$N=34$	$34$
$2$	$13$	$N=10^5$，所有男孩相邻，所有女孩也相邻	$18$
$3$	$8$	$N=10^5$，每个人的性别是随机生成的	$34$
$4$	$11$	$N=10^5, K=50000$	$18$
$5$	$10$	$N=65536, K=128$	$26$
$6$	$10$	$N=10^5, K=400$	$26$
$7$	$9$	$N=10^5, K=99601$	$26$
$8$	$10$	$N=10^5, K=330$	$68$
$9$	$24$	无附加限制	$34$

设 $Q$ 为该测试中调用 ask 函数的次数。如果 $Q \leq Q_{full}$，你将获得该测试点的满分。如果 $N \geq Q>Q_{full}$，你将获得 $score \cdot \left(1-\left(\frac{\left(Q-Q_{full}\right)}{N}\right)^{0.05}\right)$ 的分数。如果 $Q>N$ 或者你的程序给出的答案是错误的，你将获得 $0$ 分。每个子任务的得分是所有测试点中最低的得分。

调用 ask 函数超过 $10^{5}$ 次将被判为 Wrong Answer。

示例评测程序

示例评测程序按以下格式读取输入：

• 第 $1$ 行：$N\,K$
• 第 $2$ 行：$A[0]A[1]\ldots A[N-1]$，其中数组 $A$ 是一个字符串，表示我们隐藏的参与者圈子。特别地，如果 $A[i]=\texttt{X}$，则对应的参与者是男孩；如果 $A[i]=\texttt{Y}$，则对应的参与者是女孩。

示例评测程序按以下格式输出每个问题：

• 第 $1$ 行：$?\,L\,R$

示例评测程序按以下格式输出每个答案：

• 第 $1$ 行：$x$

示例评测程序按以下格式输出参赛者的答案：

• 第 $1$ 行：$!\,S$

在交互结束时，示例评测程序会输出参赛者调用 ask 函数的次数。