配点 : 100 点
問題文
请注意,内存限制是特殊的。 请解决
T 测试用例的以下问题。
长度
小于或等于 N 整数序列
给出 A = (A_0, A_1, \dots, A_{N-1}) 。
对于
重复以下操作之一,直到数组的长度为 1。
- \mathrm{AND} 操作:两个相邻元素 选择 (a, b) ,合并它们并用一个元素替换它们。此时新元素为 a \,\&\, b 。
- \mathrm{OR} 操作:两个相邻元素 选择 (a, b) ,合并它们并用一个元素替换它们。此时新元素为 a \,|\, b 。
当数组最后有一个元素时,其值为 必须是 0 。
在满足该条件的操作序列中, 求执行\mathrm{OR} 操作的最大次数。
但是,如果不存在这样的操作列, -1 输出。
制約
- 1 \leq T \leq 2^{12}
- 2 \leq N \leq 2^{13}
- 0 \leq A_{i} < 2^{13}
- 在每个测试用例中 N 的总和是 2^{13} 不超过
- 所有输入均为整数
部分点
对于此问题,以下规则确定提交的分数。
- 在所有输入情况下 如果您得到 AC ,您将获得满分。
-
如果没有, 我们可以使用以下规则获得m = 1,2 \ldots 12 的部分分数。
- “在每个测试用例中 N 的总和是 不超过 2^m 并且A_i < 2^m'' 对于满足条件的所有输入案例 如果您得到 AC ,另外 可获得 m 积分。
-
例如,“在每个测试用例中 如果您得到 N 的总和是 不超过 2^4 (=16) 并且A_i < 2^4'' 对于满足条件的所有输入案例 如果您得到 AC ,1+2+3+4 点,即 10 积分。
入力
输入是按以下格式从标准输入给出的。输入的 1 行具有以下格式。
T
然后,T 测试用例如下。每个测试用例均按以下格式给出。
N
A_{1} A_{2} \cdots A_{N}
出力
T 行。i 行中,i 个测试用例中完成。 \mathrm{OR} 查找最大操作数。
入力例 1
4 6 3 0 1 4 1 5 2 0 1 8 2 0 1 6 1 2 0 3 10 1 7 6 7 5 7 5 3 2 7
出力例 1
3 0 5 6
该输入包含 包含4 测试用例。
1 对于第二个测试用例,请按照以下步骤操作。 2 第次操作 3 可以进行回合。
- 最初、A = (3,0,1,4,1,5) 。
- (A_{3}, A_{4}) 反对 \mathrm{OR} 执行操作。手术后,A = (3,0,5,1,5) 变为。
- (A_{1}, A_{2}) 反对 \mathrm{AND} 执行操作。手术后,A = (0,5,1,5) 变为。
- (A_{3}, A_{4}) 反对 \mathrm{OR} 执行操作。手术后,A = (0,5,5) 变为。
- (A_{2}, A_{3}) 反对 \mathrm{OR} 执行操作。手术后,A = (0,5) 变为。
- (A_{1}, A_{2}) 反对 \mathrm{AND} 执行操作。手术后,A = (0) 变为。
这个操作方法最终 由于 A_{1} = 0 成立,因此满足条件。 \mathrm{OR} 操作 通过执行超过 4 这是一种多次执行的方法,答案是 3 。 对于