/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 1100 点
問題文
以下の操作を行った結果 A として得られる可能性がある数列を特別な数列と呼ぶことにします。
- N 頂点 0 辺からなる無向グラフと長さ 0 の数列 A を用意する。
- 1 \leq i < j \leq N を満たす整数 i,j と q \in \{1,2\} に対し、以下のクエリを用意する。
- q=1 のとき、頂点 i と頂点 j を辺で結ぶ。
- q=2 のとき、頂点 i と頂点 j が連結であるならば 1 を、連結でないならば 0 を、A の末尾に追加する。
- 考えられるクエリは N(N-1) 通りあるが、これらを好きな順に並べ替え、その順に処理する。
0 と 1 からなる長さ \frac{N(N-1)}{2} の数列 B が与えられます。 B に対して以下の操作を何回でも行うことができます。
- 1 \leq i \leq \frac{N(N-1)}{2}-1 を満たす整数 i を選び、B_i と B_{i+1} を入れ替える。
B を特別な数列にすることが可能かを判定し、可能ならばそのために必要な操作回数の最小値を求めてください。
1 つの入力につき、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 行目には、t 番目のテストケースについてB を特別な数列にすることが可能ならばそのために必要な操作回数の最小値を、不可能ならば -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
1 つ目のテストケースでは、(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,1,0,1,1,0) は特別な数列ではないため、答えは 1 になります。
Score : 1100 points
Problem Statement
A sequence that can be obtained as A by performing the following operations is called a special sequence:
- Prepare an undirected graph consisting of N vertices and 0 edges, and a sequence A of length 0.
- Prepare queries for integers i,j satisfying 1 \leq i < j \leq N and q \in \{1,2\}:
- When q=1, connect vertices i and j with an edge.
- When q=2, append 1 to the end of A if vertices i and j are connected, and append 0 otherwise.
- There are N(N-1) possible queries; rearrange them in any order and process them in that order.
You are given a sequence B of length \frac{N(N-1)}{2} consisting of 0 and 1. You can perform the following operation on B any number of times:
- Choose an integer i satisfying 1 \leq i \leq \frac{N(N-1)}{2}-1, and swap B_i and B_{i+1}.
Determine whether it is possible to make B a special sequence, and if possible, find the minimum number of operations required.
Solve T test cases per input.
Constraints
- 1 \leq T
- 2 \leq N \leq 500
- |B| =\frac{N(N-1)}{2}
- 0 \leq B_i \leq 1
- The sum of |B| over all test cases is at most 3 \times 10^5.
- The sum of N^3 over all test cases is at most 500^3.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
T case_1 case_2 \vdots case_T
Each case is given in the following format:
N
B_1 B_2 \ldots B_{\frac{N(N-1)}{2}}
Output
Output T lines in total.
The t-th line should contain the minimum number of operations required to make B a special sequence for the t-th test case if it is possible to do so, and -1 otherwise.
Sample Input 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
Sample Output 1
1 0 0 3
In the first test case, if the queries are processed in the order (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), the resulting sequence is (1,1,0,1,0,1), and B can be changed to this sequence by performing the operation once. Also, (1,1,0,1,1,0) is not a special sequence, so the answer is 1.