← 返回题目列表

AtCoder · agc074_d

D. DSU 问题的有效输出

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

分数: 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.