UOJ Logo Universal Online Judge

UOJ

#306. 【WC2004】搬家公司

附件下载 统计

这是一道交互题。

你率领着巨人组成的搬家公司为大富翁搬家。你拥有 $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}$