分数: 1000 点
问题陈述
AtCoder世界巡回赛总决赛2800, N 选手参赛,共提出五个问题。每个问题至少分配一个整数分数 1 点,并对问题进行编号,以便分数 非递减 来自问题 1 问题 5。没有部分点。与通常的 AtCoder 规则类似,排名如下。 在这个问题中,我们不考虑多个参赛者总分和罚分相同的情况。
排名
总分越高的选手排名越高。如果出现平局,则罚分较小的排名靠前。现在,报道决赛的记者青木注意到以下信息:
- 参与人数 N.
- 每个参赛者解决了哪些问题。 A_{i,j}=1 表示 i第 参赛者 (1 \leq i \leq N) 正确解决了问题 j,和 A_{i,j}=0 意味着他们没有。
- 每位参赛者的排名。的 i第 参赛者 (1 \leq i \leq N) 排名 R_i-th。
然而,当他开始写这篇文章时,他意识到自己没有记下分数和处罚。此外,他意识到他所记录的信息可能存在不一致之处。现在,解决以下问题。
假设他正确记下信息 1 和 2。 让 D_i 为参赛者的实际排名 i (1 \leq i \leq N),并找到最小可能的总平方误差 (D_1 - R_1)^2 + (D_2 - R_2)^2 + \dots + (D_N - R_N)^2.
你有 T 要处理的测试用例。
约束
- 1 \leq T \leq 10^5
- 2 \leq N \leq 3 \times 10^5
- 每个 A_{i,1}, A_{i,2}, A_{i,3}, A_{i,4}, A_{i,5} is 0 or 1 (1 \leq i \leq N).
- 总和 A_{i,1}, A_{i,2}, A_{i,3}, A_{i,4}, A_{i,5} 至少 1 (1 \leq i \leq N).
- 1 \leq R_i \leq N (1 \leq i \leq N)
- R_1, R_2, \dots, R_N 是不同的。
- 总价值 N 在所有测试用例中最多 3 \times 10^5.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出。这里 \mathrm{case}_i 代表 i- 第一个测试用例 (1 \leq i \leq T).
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
每个测试用例均按以下格式给出:
N
A_{1,1} A_{1,2} A_{1,3} A_{1,4} A_{1,5}
A_{2,1} A_{2,2} A_{2,3} A_{2,4} A_{2,5}
\vdots
A_{N,1} A_{N,2} A_{N,3} A_{N,4} A_{N,5}
R_1 R_2 \cdots R_N
输出
打印答案。
样本输入 1
6 4 0 1 1 0 0 1 0 0 1 0 1 1 0 1 0 1 0 1 0 0 1 2 3 4 8 0 1 0 0 0 1 1 0 1 0 0 1 1 0 1 1 0 0 0 0 1 1 0 1 0 0 1 0 0 0 0 0 0 1 0 0 1 1 1 1 7 4 2 8 3 6 5 1 6 1 1 0 0 0 0 0 1 0 0 1 1 1 0 0 0 0 0 1 0 1 1 1 1 0 0 0 0 0 1 1 2 3 4 5 6 6 1 1 0 0 0 0 0 1 0 0 1 1 1 0 0 0 0 0 1 0 1 1 1 1 0 0 0 0 0 1 6 5 4 3 2 1 20 0 0 0 0 1 0 0 1 0 0 1 1 0 0 1 1 0 1 0 1 0 0 0 1 1 0 0 1 1 1 1 1 1 1 0 1 1 0 1 0 0 0 1 1 0 1 0 1 0 0 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 1 0 1 0 1 0 0 0 1 1 1 1 0 0 0 1 1 1 0 0 0 0 1 0 1 1 1 0 1 1 1 0 1 1 7 18 3 5 19 11 13 2 4 10 14 15 17 6 16 9 8 12 1 20 15 0 0 1 1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 1 1 1 1 0 0 1 0 1 1 1 0 1 1 1 1 1 0 1 1 0 1 1 1 0 1 0 1 0 0 1 1 1 0 1 0 0 1 1 0 1 1 0 1 0 1 0 1 1 0 0 0 0 1 0 0 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
示例输出 1
6 0 26 0 1054 428
此输入包含六个测试用例。让我们解释一下第一个。
考虑以下场景。
- 问题 分别为 1, 2, 3, 4, 5 有 100, 500, 800, 900, 1300 点。
- 参赛者 1, 2, 3, 4 的处罚为 90, 80, 70, 60 分钟。
那么,排名将如下表所示,其中总平方误差为 (2-1)^2 + (3-2)^2 + (1-3)^2 + (4-4)^2 = 6。没有办法使总平方误差 5 或更少,所以答案是 6.
参赛者 问题1 问题2 问题3 问题4 问题5 总分 处罚 排名 参赛者1 - 500 800 - - 1300 90 分钟 第二 参赛者2 100 - - 900 - 1000 80 分钟 第三 参赛者 3 100 500 - 900 - 1500 70 分钟 第一 参赛者 4 100 - 800 - - 900 60 分钟 第四
现在,让我们解释第二个测试用例。
考虑以下场景。
- 问题 分别为 1, 2, 3, 4, 5 有 1000, 1400, 2000, 2000, 2718 点。
- 参赛者 1, 2, \dots, 8 的处罚为 295, 286, 242, 236, 277, 288, 187, 299 分钟。
那么,排名将如下表所示。对于每一个 i (1 \leq i \leq N), 参赛者排名 i is R_i,所以总平方误差是 0.
参赛者 问题1 问题2 问题3 问题4 问题5 总分 处罚 排名 参赛者1 - 1400 - - - 1400 295 分钟 第七 参赛者2 1000 1400 - 2000 - 4400 286 分钟 第四 参赛者 3 - 1400 2000 - 2718 6118 242 分钟 第二 参赛者 4 1000 - - - - 1000 236 分钟 8日 参赛者5 1000 1400 - 2000 - 4400 277 分钟 第三 参赛者 6 - 1400 - - - 1400 288 分钟 第六 参赛者 7 - - - 2000 - 2000 187 分钟 第五 参赛者 8 - 1400 2000 2000 2718 8118 299 分钟 第一