← 返回题目列表

AtCoder · arc177_e

E. 记分板错误

中文机器翻译题面 查看原题

分数: 1000 点

问题陈述

AtCoder世界巡回赛总决赛2800, N 选手参赛,共提出五个问题。每个问题至少分配一个整数分数 1 点,并对问题进行编号,以便分数 非递减 来自问题 1 问题 5。没有部分点。与通常的 AtCoder 规则类似,排名如下。 在这个问题中,我们不考虑多个参赛者总分和罚分相同的情况。

排名总分越高的选手排名越高。如果出现平局,则罚分较小的排名靠前。

现在,报道决赛的记者青木注意到以下信息:

  1. 参与人数 N.
  2. 每个参赛者解决了哪些问题。 A_{i,j}=1 表示 i第 参赛者 (1 \leq i \leq N) 正确解决了问题 j,和 A_{i,j}=0 意味着他们没有。
  3. 每位参赛者的排名。的 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 分钟 第一