QOJ.ac

QOJ

Time Limit: 5 s Memory Limit: 512 MB Total points: 100 Interactive

#10231. 搬家公司

统计

这是一道交互题。

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

交互库不是自适应的。

About Issues

We understand that our problem archive is not perfect. If you find any issues with the problem, including the statement, scoring configuration, time/memory limits, test cases, etc.

You may use this form to submit an issue regarding the problem. A problem moderator will review your issue and proceed it properly.

STOP! Before you submit an issue, please READ the following guidelines:

  1. This is not a place to publish a discussion, editorial, or requests to debug your code. Your issue will only be visible by you and problem moderators. Other users will not be able to view or reply your issues.
  2. Do not submit duplicated issues. If you have already submitted one, please wait for an moderator to review it. Submitting multiple issues will not speed up the review process and might cause your account to be banned.
  3. Issues must be filed in English or Chinese only.
  4. Be sure your issue is related to this problem. If you need to submit an issue regarding another problem, contest, category, etc., you should submit it to the corresponding page.

Active Issues 0

No issues in this category.

Closed/Resolved Issues 0

No issues in this category.