题目背景

$\small\text{The Border of \textbf{Divinity}}.$

题目描述

这是一道交互题，仅支持 C++ 语言提交，且不支持 C++14（GCC 9）。

Hikari 和 Tairitsu 用她们的玻璃渣子发明了新的游戏。

有 $n$ 堆碎片，编号为 $0\sim n-1$。

$a$ 为一个长度为 $n$，下标为 $0\sim n-1$ 的正整数序列，表示第 $i$ 堆碎片的数量为 $a_i$。

她们轮流进行操作，每轮操作如下：

• 选择一堆碎片 $i$，拿出不少于一个碎片并丢弃；
• 然后将 $i$ 这一堆中剩下的碎片随意分配到所有非空的堆中，特别地，可以放回原来的堆。

Hikari 先手，不能操作者输。

你将会成为 Hikari 或者 Tairitsu 中的一个，和另一个进行游戏。

具体地，给定 $a_0, a_1, \ldots, a_{n-1}$，你需要选定先后手并在 $a_0, a_1, \ldots, a_{n-1}$ 上和交互库进行游戏。

交互格式

本题使用多组测试数据且采用捆绑测试。

你的程序不需要，也不应该包含 main 函数。

然后你只需要实现如下 $3$ 个函数：

bool Init(int n, int op, std::vector<int> a);

• 这个函数用于你的程序的初始化与预处理。
• 其中 $n$ 为题意所述的碎片堆数，$op$ 为子任务编号。
• $a$ 为一个长度为 $n$，下标为 $0\sim n-1$ 的 std::vector<int>，表示上述的序列。
• 你需要返回一个 $\{0,1\}$ 中的数。返回 $0$ 表示在游戏中你选择先手 Hikari，返回 $1$ 表示你选择后手 Tairitsu。

void Get(std::vector<int> a);

• 这个函数用于你的程序接收交互库操作后的序列。
• $a$ 为一个长度为 $n$ 的 std::vector<int>，表示交互库操作后所给出的序列。

std::vector<int> Play();

• 这个函数用于你的程序返回你操作后的序列。
• 你需要返回一个长度为 $n$ 的 std::vector<int> $a$，表示你操作后所给出的序列。

本题每个测试点有多组测试数据。在每个测试点中，对于每组数据，交互库的交互格式如下：

• 先调用一次 Init()。
• 当选手程序选择了先手，调用 Play()；否则跳过这一步。
• 交互库对 $a$ 进行一次操作后调用 Get()。
• 接下来交互库交替调用 Play() 和 Get()，保证每连续两次调用中操作恰好调用一次 Play() 和一次 Get()。
• 特别地，如果某次调用 Play() 后交互库将 $a$ 操作至终止状态，或者交互库无法操作时，交互库会得出结果并终止这组测试数据的调用过程，跳到下一组测试数据。也就是最后交互库并不会再调用一次 Get()。

本题将使用自定义校验器对你的交互过程进行评分，具体见 【评分方式】。

输入格式

见 说明/提示。

输出格式

见 说明/提示。

样例

2 0
10
1 1 4 5 1 4 1 9 1 9
2
1 1

AC

样例解释

该样例由两个测试数据构成。

第一个测试数据，选择先手 Hikari 必胜。

第二个测试数据，选择后手 Tairitsu 必胜。

说明/提示

本题使用多组测试数据。

本题附件中提供了 grader.cpp 文件和 sample.cpp 文件。sample.cpp 是选手示例程序，你可以在此基础上实现。grader.cpp 是下发交互库，其中下发交互库的策略不是最终交互库的策略，因此你的实现不应依赖于交互库的实现。

你需要将你的程序 game.cpp 和 grader.cpp 放置在同一目录下，并在该目录下使用如下编译命令得到可执行程序 game(.exe)：

g++ -o game grader.cpp game.cpp -O2 -std=c++14

可执行程序从标准输入读入以下格式的数据：

• 第一行两个正整数 $T$ 和 $op$，$T$ 为测试数据组数，$op$ 为子任务编号。有且仅有样例满足 $op=0$。
• 接下来每组测试数据，输入格式如下：
  • 第一行输入一个正整数 $n$，表示序列 $a$ 的长度。
  • 第二行输入 $n$ 个正整数，表示 $a_0,a_1,\ldots,a_{n-1}$。

在本地测试时，请务必保证你的输入与交互格式符合要求，否则我们不保证交互库会正常运行。

如果你的输入与交互格式合法且没有运行错误，下发的交互库将会根据你的调用输出如下信息：

• 若你成功打赢了交互库，交互库输出 AC。
• 否则交互库输出 WA。

你的程序不应该操作标准输入输出，否则视为攻击交互库。

评分方式

本题将使用自定义校验器对你的交互过程进行评分。在每个测试点中，如果你超出了时间限制，超出了空间限制，或发生了运行时错误，则你的得分为 $0$。否则你的分数取决于你的程序在交互过程中的表现：

• 参数 $S$ 与你的程序在交互过程中的表现有关：
  • 若你在测试点中的每个测试数据中，均选择了正确的先后手并且均打赢了交互库，则 $S=1$。
  • 若你在测试点中的每个测试数据中，均选择了正确的先后手但是有不合法操作或者打输了交互库，则 $S=0.2$。
  • 若你在测试点中的每个测试数据中，至少一次选择了错误的先后手但是均打赢了交互库，则若 $op\in \{4,5\}$，$S=1$；否则 $S=0.6$。
  • 否则 $S=0$。
• 最终你在该测试点的得分为 $S\times score$，$score$ 为测试点所在子任务的分数。
• 最终你在某个子任务的得分为你在子任务内所有测试点的得分的最小值。

数据范围

本题采用捆绑测试。

子任务编号（$op =$）	$n\le$	$a_i\le$	特殊性质	分值
$1$	$3$	$2$	无	$5$
$2$	$10$			$15$
$3$	$100$			$10$
$4$	$2000$		A	$15$
$5$			B	$20$
$6$			无	$35$

• 特殊性质 A：交互库的策略为选择一个非空的堆，拿走若干个碎片并将剩余的碎片放回原堆中。
• 特殊性质 B：交互库的策略为选择一个非空的堆，拿走若干个碎片并将剩余的碎片全部放到一个堆中（可能为原堆）。

对于所有数据，满足 $1 \le T\le 2000$，$1 \le op \le 6$，$1 \le n\le 2000$，$1 \le a_i\le 2000$，$1 \le \sum a_i \le 4000$，$1 \le\sum n\le 2000$，$1 \le \sum\sum a_i\le 4000$。

保证每个测试点中 Init() 的调用次数不超过 2000 次，Get() 和 Play() 的调用次数总和不超过 4000 次。当选手交互格式正确时，交互库运行所占用的时间始终不超过 500ms。

sample.cpp

grader.cpp