P1058单舟见京杭（canal）

本题为交互题。

【题目背景】

龙泽于汤，唤水筑乡，单舟见京杭。

【题目描述】

若干位旅客沿着运河一路向北前行。这条运河共有 $n$ 段水道，每段水道的左右两侧各有一处景观。对于第 $i$ 段水道，其左右两侧景观的美观度分别为 $w_i$ 与 $v_i$。

每位旅客经过一段水道时，都可以选择向左看或向右看。旅客最终收获的幸福值，等于沿途看到的所有不同景观的美观度之和。

运河蜿蜒曲折。在全部 $2n$ 处景观中，恰有两处实际上是同一处景观，只是旅客所处的位置发生了改变，才会从不同水道再次看到它。这两处景观位于不同的水道，且美观度相同。其余景观的美观度不要求互不相同。

若一位旅客同时选择看到这两处重复景观，那么这处景观的美观度只会对其幸福值产生一次贡献。

在旅程开始前，你已经知道所有 $w_i,v_i$，却不知道哪两处景观是重复景观。你可以提前安排若干位旅客，分别决定每位旅客经过每段水道时看向哪一侧。每位旅客抵达终点后，都会向你报告获得的幸福值。

现在，你需要根据这些报告确定两处重复景观各自所在的水道与方向。每多安排一位旅客，都会打扰原本平静的行程，因此你希望使用的旅客数量尽可能少。

【实现细节】

选手不需要，也不应实现 main 函数。

选手需要确保提交的程序包含头文件 canal.h，即在程序开头加入以下代码：

1#include "canal.h"

选手需要在提交的程序源文件 canal.cpp 中实现以下两个函数：

1void Init(int c, int T);

• $c,T$ 分别表示测试点编号与测试数据组数。$c=0$ 表示该测试点为样例。
• 对于每个测试点，该函数会在程序开始运行时被交互库调用恰好一次。

1void Locate(int c, int n, std::vector<int> w,2            std::vector<int> v);

• $c,n$ 分别表示测试点编号与水道数量。
• w 与 v 的长度均为 $n+1$。对于 $1\leq i\leq n$，w[i] 与 v[i] 分别表示第 $i$ 段水道左侧与右侧景观的美观度。w[0] 与 v[0] 没有实际意义。
• 对于每组测试数据，该函数会被交互库调用恰好一次。

在 Locate 函数中，选手可以调用以下函数安排一位旅客：

1long long Travel(std::vector<int> choice);

• choice 的长度必须为 $n+1$。choice[0] 没有实际意义。
• 对于 $1\leq i\leq n$，choice[i] 必须为 $0$ 或 $1$。$0$ 表示旅客经过第 $i$ 段水道时向左看，$1$ 表示向右看。
• 该函数返回这位旅客最终获得的幸福值。
• 选手需要确保交互库每次调用 Locate 时，调用该函数的次数不超过 $200$。

选手需要调用以下函数给出答案：

1void Answer(int x, int a, int y, int b);

• $(x,a)$ 与 $(y,b)$ 分别描述一处重复景观。其中 $1\leq x,y\leq n$，$x\neq y$，$a,b\in\{0,1\}$。
• $a=0$ 表示第 $x$ 段水道左侧的景观，$a=1$ 表示右侧的景观。$b$ 的含义与之相同。
• 交换 $(x,a)$ 与 $(y,b)$ 的顺序仍视为同一答案。
• 选手需要确保交互库每次调用 Locate 时，恰好调用该函数一次。
• 调用该函数后，本组交互立即结束。此后不得继续调用 Travel 或 Answer，且 Locate 函数应当结束运行。

交互库运行所需的时间与空间均计入本题的时间与空间限制。

【测试程序方式】

选手可以在本题目录下使用如下命令编译得到可执行文件：

1g++ grader.cpp canal.cpp -o canal -O2 -std=c++14 -static

对于编译得到的可执行文件 canal：

• 可执行文件将从标准输入读入以下格式的数据：

  • 第一行包含两个非负整数 $c,T$，分别表示测试点编号与测试数据组数。$c=0$ 表示该测试点为样例。
  • 接下来对于每组测试数据，第一行包含一个正整数 $n$。
  • 第二行包含 $n$ 个正整数 $w_1,w_2,\cdots,w_n$。
  • 第三行包含 $n$ 个正整数 $v_1,v_2,\cdots,v_n$。
  • 第四行包含四个整数 $x,a,y,b$，表示两处重复景观。这些信息只会由本地测试交互库读取，不会传入 Locate 函数。

• 若 $T$ 次调用 Answer 给出的答案均正确，可执行文件将输出以下格式的数据至标准输出：

  • 输出的第一行为 Correct!。
  • 输出的第二行为 Max travelers used: q，其中 $q$ 表示所有测试数据中调用 Travel 次数的最大值。
  • 输出的第三行为 Score ratio: p%，其中 $p$ 表示按照【评分方式】计算出的得分百分比。

• 若至少一次调用 Answer 给出的答案不正确，则可执行文件只会向标准输出输出一行 Wrong answer。

• 若调用 Travel 或 Answer 时传入的参数不符合要求，调用次数超过上限，或函数调用顺序不合法，则可执行文件会向标准错误流输出错误信息并终止程序。

【样例 1 输入】

10 12435 3 7 241 7 4 652 1 3 0

【样例 1 输出】

1Correct!2Max travelers used: 53Score ratio: 100%

【说明/提示】

【样例 1 解释】

样例中，第 $2$ 段水道右侧与第 $3$ 段水道左侧看到的是同一处景观，这两处景观的美观度均为 $7$。

样例输出对应一种使用 $5$ 位旅客并正确调用 Answer(2,1,3,0) 的策略。不同的合法策略可能产生不同的样例输出。

【样例 2】

见选手目录下的 $\textbf{\textit{canal/canal2.in}}$。

该组样例符合测试点 $1$ 的数据范围。

【样例 3】

见选手目录下的 $\textbf{\textit{canal/canal3.in}}$。

该组样例符合测试点 $2$ 的数据范围。

【样例 4】

见选手目录下的 $\textbf{\textit{canal/canal4.in}}$。

该组样例符合测试点 $3$ 的数据范围。

【样例 5】

见选手目录下的 $\textbf{\textit{canal/canal5.in}}$。

该组样例符合测试点 $4$ 的数据范围。

本题为交互题，附加样例只提供隐藏输入。测试程序的输出由选手程序采用的策略决定。

\newpage

【数据范围】

对于 $100\%$ 的数据，保证 $1\leq T\leq 20$，$2\leq n\leq 10^5$，$1\leq w_i,v_i\leq 10^9$。对于同一个测试点，保证 $\sum n\leq 2\times 10^5$。

特殊性质 A：两处重复景观都位于水道左侧，或都位于水道右侧。

【评分方式】

注意：

• 选手不应当通过非法方式获取交互库的内部信息，如试图直接读取两处重复景观的位置，或直接与标准输入、输出流进行交互。此类行为将被视为作弊。
• 交互库不是适应性的。每次调用 Locate 时，所有景观的美观度与两处重复景观的位置均已确定，不会随交互过程改变。
• 最终的评测交互库与本地测试交互库的实现不同。

若 Answer 给出的答案不正确，调用 Travel 或 Answer 时不符合以上要求，或调用次数超过上限，则相应测试点得 $0$ 分。

在上述条件均满足的基础上，记一个测试点中调用 Travel 次数的最大值为 $q$，该测试点的得分比例为

若 $q\leq 80$，则该测试点取得全部分值。若 $80<q\leq 200$，则该测试点取得对应分值的 $\frac{80}{q}$。

记表中该测试点的分值为 $d$，则取整前的实际得分为 $dp(q)$。最终得分保留两位小数，并采用向下取整，也就是