#2985. 「WC2019」I 君的商店

内存限制:512 MiB 时间限制:2000 ms 题目类型:交互
上传者: HeRaNO

题目描述

这是一道交互题

V 君、I 君和 Y 君是好朋友。

I 君最近开了一家商店,商店里准备了 NN 种物品(编号为 0N10 \sim N − 1 中的整数),每种物品均有无限个可供出售,每种物品的单价是 00 或者 11

V 君想知道每个物品的价格,他已经通过某种超自然力量知道,这 NN 个物品里,价格是 11 的物品恰好有奇数/偶数个,且至少存在一个物品的价格是 11

然而, V 君并不想自己去问 I 君,他选择了这样一种方法:他准备了 ++\infty 的钱给 Y 君。然后让 Y 君帮他跑腿:每一次,他会给 Y 君指定两个非空物品集合 S,TS, T(同一个集合内的物品必须两两不同,即每种物品在每个集合类最多包含一个),Y 君会跑到商店,分别买下这两个集合的物品,把他们送回来,并告诉 V 君哪个集合的物品价格之和更高。但是,当两集合价格之和相等的时候,Y 君会按照 I 君的指示来回答 V 君。

带着很多物品跑腿是一个很累的事情,因此,我们定义一次跑腿的体力消耗是 S+T\texttt{S} + \texttt{T}。其中,S\texttt{S} 表示集合 SS 包含的物品个数。

你的任务是:写一个程序,帮助 V 君决定如何合理地让 Y 君跑腿,从而推算出每种物品的价值。Y 君的体力有限,你当然不能让他过于劳 累,也即,你不能让他的总体力消耗超过某个预设的阈值 MM

实现细节

你不需要,也不应该实现主函数,你只需要实现下列函数:

  • find_price(task_id, N, K, ans)
  • 其中 task_id 表示子任务编号(见限制与约定)。NN 表示物品个数,KK 的意义为:
    • K=0K = 0,表示有偶数个物品价值为 11
    • K=1K = 1,表示有奇数个物品价值为 11
  • 你需要将计算出的物品价格放在数组 ans[]\text{ans}[] 中,其中 ans[i]\text{ans[i]} 表示编号为 ii 的物品的价格。

你可以通过调用如下函数来向交互库发出询问:

  • query(S, nS, T, nT)
  • 这里 nS=S,nT=T\text{nS} = \texttt{S}, \text{nT} = \texttt{T}, 数组 S [0(nS − 1)]\text{S [0\ldots (nS − 1)]} 和数组 T[0(nT − 1)]\text{T[0\ldots (nT − 1)]} 分别描述两个集合,你需要保证:
    • nS, nT>0\text{nS, nT} > 0
    • 0i<nS,0S[i]<N\forall 0 \le i < \text{nS} , 0 \le \text{S[i]} < N
    • 0i<nT,0T[i]<N\forall 0 \le i < \text{nT} , 0 \le \text{T[i]} < N
      \forall 的意思是:「对于任意的」。例如:0i<nS,0S[i]<N\forall 0 \le i < \text{nS} , 0 \le \text{S[i]} < N 的意思是:「对于任意的在 [0,nS)[0, \text{nS}) 内的 iiS[i]\text{S[i]}[0,N)[0, N) 内」。
  • 调用此函数一次的时间复杂度为 Θ(nS + nT)\Theta(\text{nS + nT})。它的返回值为 0011,返回值的意义为:
    • 若集合 SS 的物品价格和更大,返回 00
    • 若集合 TT 的物品价格和更大,返回 11
    • 否则,按照某种未知规则返回 0011
  • 如题面所述,我们定义这样一次调用的代价为 nS + nT\text{nS + nT}

评测时,交互库可能会调用 find_price 多次(不超过 1010 次),每次调用代表一次新的猜价格游戏,所有的物品的价格都会被重新设定。

输入格式

可执行文件将从标准输入读入以下格式的数据:

第一行一个整数 T(T100)T ( T \le 100 ),表示数据组数。对每组数据:

  • 第一行包含两个整数 \texttt{task_id}, N
  • 接下来一行一个长度为 NN0101ss,其中 sis_i 表示物品 ii 的价格。你需要保证至少有一个物品价格为 11

读入完成之后,交互库将调用 TTfind_price 函数。

接下来交互库会判断你的函数每次计算是否正确,若全部正确则会输出 Correct,否则会输出相应的错误信息。

数据范围与提示

评分标准

最终评测时只会收取 shop.cpp/c/pas,修改选手目录中的其他文件对评测无效。

题目首先会受到和非交互式程序题相同的限制。例如编译错误会导致整道题目得 00 分,运行时错误、超过时间限制、超过空间限制等会导致相应测试点得 00 分等。你只能访问自己定义的和交互库给出的变量及其对应的内存空间,尝试访问其他空间将可能导致编译错误或运行错误。

在上述条件基础上,在一个测试点中,你得到满分,当且仅当每一次 find_price 的调用中:

  • 你的每一个 query 的调用符合规则,且调用代价之和不超过 MM
  • 你的函数正确计算了 ans[]\text{ans[]} 数组。

在一个测试点中,如果你没有获得满分,那么你获得 00 分。

子任务

我们令代价之和的上界为 MM,记答案数组为 ans[]\text{ans[]}

  • 子任务 1:N5M=100N \le 5, M = 100
  • 子任务 2:N103M=106N \le 10^3, M = 10^6
  • 子任务 3:N105M=100N \le 10^5, M = 100,保证 i<j<k\forall i < j < k,若 ans[i]=ans[k]\text{ans[i]} = \text{ans[k]} 则必有 ans[j]=ans[i]\text{ans[j]} = \text{ans[i]}
  • 子任务 4:N104M=2×105N \le 10^4, M = 2 \times 10^5
  • 子任务 5:N5×104M=350100N \le 5 \times 10^4, M = 350100
  • 子任务 6:N105M=500100N \le 10^5, M = 500100

提示

I 君可能并不愿意让 V 君知道每件物品的价格,在物品价格相等时,他会按照他自己的某种方式来回答问题。

子任务分值

在本场比赛中,测试点(或子任务)的分值分布与你是否为集训队选手有关。本题的分值设置如下:

子任务编号 1 2 3 4 5 6
集训队分值 2020 1111 99 1212 1717 3131
非集训队分值 3131 2121 1313 99 1111 1515

在 LibreOJ 上,将按照「集训队分值」一栏的分值进行评分。