故事
AtCoder 提供官方商品在线购物。 高桥首席执行官决定将未售出的商品一起作为抓包出售。 每个包的重量应该尽可能均匀,但遗憾的是,AtCoder 的办公室里没有秤可以数字测量重量。 作为替代方案,他找到了平衡点。 请用天平比较重量,尽量将货物分开。
问题陈述
有 N 项目。 重量 每个项目的 w_i 每个项目的 i 未知。 使用可以比较两个项目组重量总和的天平,重复以下操作。
在天平的左右板上放置任意数量的物品。然后您可以看到哪一侧的权重更大或它们的权重相等。
重复此操作后 Q 次,将项目分为 D 套总重量尽可能相等。
评分
让 t_0,t_1,\cdots,t_{D-1} 是输出部门中每组物品的总重量。设均值为 t be \bar{t}=\frac{1}{D}\sum_{i=0}^{D-1}t_i。方差是 V=\frac{1}{D}\sum_{i=0}^{D-1} (t_i-\bar{t})^2。 那么你将获得绝对分数 1+\mathrm{round}\left(100\times \sqrt{V}\right)。 绝对分数越低越好。
对于每个测试用例,您将获得 排名分数 根据您的绝对分数较低者确定的排名。提交的分数是每个测试用例的总排名分数。排名分数的计算方式如下,排名分数越高越好。
让 n_{submit} 是提交作品的参赛者数量, n_{lose} 是获得绝对分数低于您的参赛者的数量,并且 n_{tie} 是获得与您相同的绝对分数的其他参赛者的数量。那么你在这个测试用例中的排名被确定为 r=n_{lose}+0.5 n_{tie},您的排名分数是 \mathrm{round}(10^9\times (1-\frac{r}{n_{submit}})).
最终排名将通过比赛结束后进行的系统测试进行更多的输入来确定。 在临时/系统测试中,如果您提交的测试用例产生非法输出或超出了某些测试用例的时间限制,则只有这些测试用例的排名分数将为零。 系统测试仅针对 上次提交收到的结果不是 CE 。 最后提交时请注意不要出错。
测试用例数量
- 临时测试:100
- 系统测试:5000。我们将发布 种子.txt (sha256=8a39261299bef0387172c0e0c4523c49b0cb993efd4f702ec7cf5124cf5b4c55) 比赛结束后。
关于相关评价体系
在临时/系统测试中,将仅使用收到除以下结果之外的最后提交的结果来计算排名 CE.
排名中显示的分数是相对的,每当有新的提交到达时,所有相对分数都会重新计算。 另一方面,提交页面上显示的每个提交的分数是每个测试用例的绝对分数的总和,并且不显示相对分数。 为了了解当前排名中除最新提交之外的提交的相对分数,您需要重新提交。 如果您提交的测试用例产生非法输出或超出时间限制,则提交页面上显示的分数将为 0,但排名显示的是正确回答的测试用例的相对分数总和。
关于执行时间
每次运行的执行时间可能略有不同。 此外,由于系统测试同时执行大量执行,因此观察到与临时测试相比,执行时间增加了几个百分点。 由于这些原因,非常接近期限的提交可能会导致 TLE 在系统测试中。 请测量程序中的执行时间以终止进程,或者在执行时间上留有足够的余量。
输入和输出
一、物品数量 N,划分数 D,以及查询数量 Q 由标准输入以以下格式给出。
N D Q
每个值都满足以下约束。
- 30\leq N\leq 100
- 2\leq D\leq N/4
- 2N\leq Q\leq 32N
读取以上信息后,重复以下查询 Q 次。
在 q- 第一个查询 (0\leq q\leq Q-1),您选择一组项目 L 放置在天平和该组物品的左侧 R 放置在天平的右侧。 每组不能为空,公共部分 L\cap R 必须为空。 可能有不包含在其中的项目 L or R。 让 n_L=|L|, n_R=|R|, L=\{l_0,\cdots,l_{n_L-1}\},和 R=\{r_0,\cdots,r_{n_R-1}\} (0\leq l_i,r_i\leq N-1)。 然后按以下格式在单行上输出到标准输出。
n_L n_R l_0 \cdots l_{n_L-1} r_0 \cdots r_{n_R-1}
输出后面必须跟有新行,并且您必须刷新标准输出。 否则,提交的内容可能会被判定为 TLE.
输出后,天平倾斜哪一侧的信息在标准输入的一行中给出。 给定的字符串是以下三种情况之一。
<:总重量 L 小于总重量 R.>:总重量 L 大于总重量 R.=:总重量 L 等于总重量 R.
查询必须准确执行 Q 次。 之后 Q 查询,将项目分为 D 套总重量尽可能相等。 让 i-th (0\leq i\leq N-1) 项目包含在 d_i-th (0\leq d_i\leq D-1)设置。 然后按以下格式在单行上输出到标准输出。
d_0 \cdots d_{N-1}
示例
| q | 输出 | 输入 |
|---|---|---|
| 先前信息 | 31 2 128 |
|
| 0 | 2 1 6 22 11 |
> |
| 1 | 2 2 11 22 0 1 |
< |
| \vdots | ||
| 127 | 1 1 14 24 |
< |
| 司 | 0 0 0 0 0 0 1 1 1 0 1 1 1 0 0 0 1 1 0 0 0 0 0 1 1 1 0 0 0 1 0 |
输入生成
让 \mathrm{rand\_int}(L,U) 是一个生成均匀随机整数的函数 L 和 U,包括在内。 让 \mathrm{rand\_double}(L,U) 是一个至少生成均匀随机实数的函数 L 且小于 U.
项目数量 N 是由生成的 \mathrm{rand\_int}(30,100)。 部门数量 D 是由生成的 \mathrm{rand\_int}(2,\mathrm{floor}(N/4))。 查询次数 Q 是由生成的 \mathrm{round}(N\times 2^{\mathrm{rand\_double(1,5)}}).
对于每个项目 i,我们独立生成一个值 w'_i 来自 指数分布 与 \lambda=10^{-5},我们设置物品的重量 i by w_i=\max(1, \mathrm{round}(w'_i))。如果生成的值 w'_i 超过 \frac{10^5 N}{D},我们重新生成它。
工具(输入生成器、本地测试器和可视化器)
- 网页版:这比提供动画的本地版本更强大。
- 本地版本: 你需要一个编译环境 Rust 语言.
- Windows 预编译二进制文件:如果你不熟悉Rust语言环境,请使用这个。
请注意,比赛期间禁止分享可视化结果或讨论解决方案/想法。
工具使用的输入/输出文件规范
提供给本地测试器的输入文件具有以下格式。
N D Q
w_0 \cdots w_{N-1}
最后 w_0 \cdots w_{N-1} 是每个项目的权重,不提供给求解程序。
本地测试器将程序的输出直接写入输出文件。
您的程序可能会输出以以下内容开头的注释行 #。可视化工具的 Web 版本显示带有相应查询的注释行,这对于调试和分析可能很有用。由于判断程序会忽略所有注释行,因此您可以提交按原样输出注释行的程序。
此外,注释行以 #c 经过特殊处理,您可以通过以下格式输出来为可视化工具提供暂定划分。
#c d_0 \cdots d_{N-1}