UOJ Logo Universal Online Judge

UOJ

#306. 【WC2004】搬家公司

附件下载 统计

这是一道交互题。

你率领着巨人组成的搬家公司为大富翁搬家。你拥有 n 个巨人,依次标号为 1,2,,n,巨人 i 只能搬动 i 吨或者更轻的重物。大富翁有 n 件家具需要搬运,也依次标号为 1,2,,n,重为 i 吨的家具恰有一件。显然,当每个巨人 i 恰好被要求去搬运 i 吨的家具时,搬家工作才能顺利展开。很不幸的是,你没有称量器械,也无法从家具的外表辨别出它们的重量。你唯一能做的就是发布指令,要求巨人 Ai 搬运第 i 号家具,使得一个巨人恰搬运一件家具。

  • 如果巨人 i 搬运的家具小于 i 吨,那么它会将家具举过头顶;如果巨人 i 搬运的家具恰为 i 吨,那么它会将家具拎至腰间;如果巨人 i 搬运的家具超过 i 吨,那么它只能把家具放在地上了。
  • 如果每个巨人都把家具拎至腰间,那么测试成功,搬家工作顺利展开;否则,根据巨人的表现,你可以决定并发布下一次测试指令。
  • 需要特别注意:为了不惹恼大富翁,你最多只有 20 次发布测试指令的机会。

任务

本题仅支持 C++。

你需要包含头文件 remover_c.h

你需要实现主函数,并且你可以调用如下函数:

long Start();
  • 这个函数必须最先被调用恰好一次。
  • 这个函数的返回值是 n
void Test(TA &A);
  • TA 是一个预定义好的数组类型。你需要将指令写入数组 AA[i] 表示你希望巨人 A[i] 搬运家具 i。你需要保证 A 是一个 1n 的排列。
  • 这个函数会将结果写入数组 AA[i]=1 表示 i 号家具被举过头顶,A[i]=0 表示 i 号家具被拎至腰间,A[i]=1 表示第 i 号家具被放在地上。特别的,如果这次测试成功,评测库将会直接结束程序。你不得自行结束程序。
  • 如果在 20 次调用 Test 后,测试仍未成功,评测库同样会结束程序。

样例评测库

见附件下载。

样例输入格式

第一行一个整数 n

第二行 n 个整数,第 i 个整数 wi 表示物品 i 的重量,w 必须是个 1n 的排列。

样例输出格式

若你在 20 次测试以内成功,评测库输出一行形如 OK! cnt=x,其中 x 为你使用的 Test 指令条数。

否则交互库会输出错误原因。

样例

input

3
2 3 1

explanation

以下是一次成功的交互。

函数调用 调用前数组 A 调用后数组 A
Start()   N=3
Test(A) [1,2,3] [1,1,–1]
Test(A) [2,3,1] 测试成功,正常退出

数据范围与提示

  • 对于 30% 的数据:1n10
  • 对于 60% 的数据:1n100
  • 对于 100% 的数据:1n1000

保证在合法的交互过程中,交互库不会占用超过 0.1s 时间和 16MB 空间。

交互库不是自适应的。

时间限制:5s

空间限制:512MB