分数: 1100 点
问题陈述
序列可以通过以下方式获得 A 通过执行以下操作称为 特殊序列:
- 准备一个无向图,包括 N 顶点和 0 边和序列 A 长度 0.
- 准备整数查询 i,j 满意 1 \leq i < j \leq N 和 q \in \{1,2\}:
- 当 选择 q=1,连接顶点 i 和 j 有边缘。
- 当 选择 q=2,追加 1 到年底 A 如果顶点 i 和 j 已连接,并附加 0 否则。
- 有 N(N-1) 可能的查询;以任意顺序重新排列它们并按该顺序处理它们。
给你一个序列 B 长度 \frac{N(N-1)}{2} 组成 0 和 1。 您可以执行以下操作 B 任意次数:
- 选择一个整数 i 满意 1 \leq i \leq \frac{N(N-1)}{2}-1,并交换 B_i 和 B_{i+1}.
判断是否可以使 B 一个特殊的序列,如果可能的话,找到所需的最少操作数。
解决 T 每个输入的测试用例。
约束
- 1 \leq T
- 2 \leq N \leq 500
- |B| =\frac{N(N-1)}{2}
- 0 \leq B_i \leq 1
- 总和 |B| 所有测试用例最多 3 \times 10^5.
- 总和 N^3 所有测试用例最多 500^3.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
T case_1 case_2 \vdots case_T
每个案例均按以下格式给出:
N
B_1 B_2 \ldots B_{\frac{N(N-1)}{2}}
输出
输出 T 行。
的 t- 第行应包含进行所需的最少操作数 B 的特殊序列 t-第一个测试用例(如果可以的话),并且 -1 否则。
示例输入 1
4 4 1 1 0 1 1 0 2 1 3 0 0 0 5 1 1 1 1 1 1 1 1 1 0
示例输出 1
1 0 0 3
在第一个测试用例中,如果查询按顺序处理 (q,i,j)=(1,1,4), (2,1,4), (1,2,4), (2,1,2), (1,1,2), (2,2,3), (2,2,4), (2,3,4), (1,3,4), (1,1,3), (2,1,3), (1,2,3),结果序列是 通过执行一次操作可以将 (1,1,0,1,0,1),和 B 更改为该顺序。另外, (1,1,0,1,1,0) 不是一个特殊的序列,所以答案是 1.