P16886 [GKS 2022 #E] Students and Mentors

一组 $N$ 名学生一起为即将到来的编程竞赛（如 Google 的 Kick Start 和 Code Jam）做准备。为了互相帮助备考，决定让每名学生从其他学生中挑选一位导师。导师将帮助学员解决问题、学习算法、跟踪进度，并在整个备考过程中给予支持。 每名学生将恰好有一名导师（来自其他所有学生），且一个人可以成为多人的导师。对于每名学生 $i$，我们知道其评分 $R_i$，该评分大致反映了该学生在编程竞赛中的水平。由于认为导师不应比学员强太多，学生 $j$ 可以成为学生 $i$ 的导师，仅当 $R_j \le 2 \times R_i$。注意，导师的评分甚至可以低于或等于学员的评分。 不出所料，每名学生都希望拥有尽可能强的导师。对于每名学生，你能帮忙找出他们能选到的最高可能的导师评分吗？

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例由 $2$ 行组成。 每个测试用例的第一行包含一个整数 $N$，表示一组学生的数量。 每个测试用例的第二行包含 $N$ 个整数 $R_1, R_2, R_3, \dots, R_N$，其中 $R_i$ 是第 $i$ 名学生的评分。

对于每个测试用例，输出一行，格式为 `Case #x: M1 M2 M3 ... MN`，其中 $x$ 是测试用例编号（从 $1$ 开始），$M_i$ 是第 $i$ 名学生能选到的最高可能的导师评分，如果没有合适的导师，则为 $-1$。

在样例 #1 中，有 $3$ 名学生，评分分别为 $2000$、$1500$ 和 $1900$。所有学生都可以选择其他任何学生作为导师，因此他们都选择尽可能高评分的导师。结果，他们分别选择了评分为 $1900$、$2000$ 和 $2000$ 的导师。注意，在这种情况下，评分为 $2000$ 的学生将成为其他 $2$ 名学生的导师。 在样例 #2 中，有 $5$ 名学生，评分分别为 $1000$、$600$、$1000$、$2300$ 和 $1800$（注意，有些学生可能有相同的评分）。对于两名评分为 $1000$ 的学生，他们能选到的最高评分导师为 $1800$。他们不能选择评分为 $2300$ 的导师，因为 $2300 > 2 \times 1000$。评分为 $600$ 的学生不能选择评分为 $1800$ 或 $2300$ 的导师，因此他选择评分为 $1000$ 的导师（两名评分为 $1000$ 的学生均可）。评分为 $2300$ 的学生可以选择其他任何学生作为导师，因此他选择评分为 $1800$ 的导师——这是可能中的最高评分。最后，评分为 $1800$ 的学生也可以选择其他任何学生作为导师，因此他选择可能中的最高评分 $2300$。因此，最终学生们分别选择了评分为 $1800$、$1000$、$1800$、$1800$ 和 $2300$ 的导师。 在样例 #3 中，有 $2$ 名学生，评分分别为 $2500$ 和 $1200$。对于评分为 $2500$ 的学生，另一名评分为 $1200$ 的学生可以成为导师，且没有其他选项。对于评分为 $1200$ 的学生，我们不能分配评分为 $2500$ 的导师，因为 $2500 > 2 \times 1200$，因此该学生没有合适的导师。最终，我们输出 $1200$ 和 $-1$ 作为该测试用例的结果。 ### 限制条件 $1 \le T \le 100$。 对于所有 $i$，$1 \le R_i \le 10^6$。 **测试集 1** $2 \le N \le 1000$。 **测试集 2** $2 \le N \le 10^5$。 翻译由 DeepSeek V4 Pro 完成