这是一道交互题。
你率领着巨人组成的搬家公司为大富翁搬家。你拥有 $n$ 个巨人,依次标号为 $1,2,\cdots,n$,巨人 $i$ 只能搬动 $i$ 吨或者更轻的重物。大富翁有 $n$ 件家具需要搬运,也依次标号为 $1,2,\cdots,n$,重为 $i$ 吨的家具恰有一件。显然,当每个巨人 $i$ 恰好被要求去搬运 $i$ 吨的家具时,搬家工作才能顺利展开。很不幸的是,你没有称量器械,也无法从家具的外表辨别出它们的重量。你唯一能做的就是发布指令,要求巨人 $A_i$ 搬运第 $i$ 号家具,使得一个巨人恰搬运一件家具。
- 如果巨人 $i$ 搬运的家具小于 $i$ 吨,那么它会将家具举过头顶;如果巨人 $i$ 搬运的家具恰为 $i$ 吨,那么它会将家具拎至腰间;如果巨人 $i$ 搬运的家具超过 $i$ 吨,那么它只能把家具放在地上了。
- 如果每个巨人都把家具拎至腰间,那么测试成功,搬家工作顺利展开;否则,根据巨人的表现,你可以决定并发布下一次测试指令。
- 需要特别注意:为了不惹恼大富翁,你最多只有 $20$ 次发布测试指令的机会。
任务
本题仅支持 C++。
你需要包含头文件 remover_c.h
。
你需要实现主函数,并且你可以调用如下函数:
long Start();
- 这个函数必须最先被调用恰好一次。
- 这个函数的返回值是 $n$。
void Test(TA &A);
- $\texttt{TA}$ 是一个预定义好的数组类型。你需要将指令写入数组 $\texttt{A}$,$\texttt{A[i]}$ 表示你希望巨人 $\texttt{A[i]}$ 搬运家具 $i$。你需要保证 $\texttt{A}$ 是一个 $1$ 到 $n$ 的排列。
- 这个函数会将结果写入数组 $\texttt{A}$。$\texttt{A[i]}=-1$ 表示 $i$ 号家具被举过头顶,$\texttt{A[i]}=0$ 表示 $i$ 号家具被拎至腰间,$\texttt{A[i]}=1$ 表示第 $i$ 号家具被放在地上。特别的,如果这次测试成功,评测库将会直接结束程序。你不得自行结束程序。
- 如果在 $20$ 次调用
Test
后,测试仍未成功,评测库同样会结束程序。
样例评测库
见附件下载。
样例输入格式
第一行一个整数 $n$。
第二行 $n$ 个整数,第 $i$ 个整数 $w_i$ 表示物品 $i$ 的重量,$w$ 必须是个 $1$ 到 $n$ 的排列。
样例输出格式
若你在 $20$ 次测试以内成功,评测库输出一行形如 OK! cnt=x
,其中 $x$ 为你使用的 Test
指令条数。
否则交互库会输出错误原因。
样例
input
3 2 3 1
explanation
以下是一次成功的交互。
函数调用 | 调用前数组 $\texttt{A}$ | 调用后数组 $\texttt{A}$ |
---|---|---|
Start() |
$~$ | $\texttt{N=3}$ |
Test(A) |
$\texttt{[1,2,3]}$ | $\texttt{[1,1,–1]}$ |
Test(A) |
$\texttt{[2,3,1]}$ | 测试成功,正常退出 |
数据范围与提示
- 对于 $30\%$ 的数据:$1\leq n\leq 10$。
- 对于 $60\%$ 的数据:$1\leq n\leq 100$。
- 对于 $100\%$ 的数据:$1\leq n\leq 1000$。
保证在合法的交互过程中,交互库不会占用超过 $0.1\texttt{s}$ 时间和 $16\texttt{MB}$ 空间。
交互库不是自适应的。
时间限制:$5\texttt{s}$
空间限制:$512\texttt{MB}$