以下页面来自赛事官方发布的原题PDF,已完整保存并渲染到本地。


可复制的 PDF 提取文本
Problem C
Bit Counting Sequence
Time limit: 2 seconds
For a non-negative integer x, let p(x) be the number of ones in the binary representation of x. For example, p(26) = 3
because 26 = (11010)2.
You are given a sequence of n integers (a1, a2, . . . , an). Your task is to determine whether there exists a non-negative
integer x such that (p(x), p(x + 1), ..., p(x + n −1)) is equal to (a1, a2, . . . , an). Furthermore, if it exists, compute
the smallest x satisfying the condition.
Input
The first line of input contains one integer t (1 ≤t ≤1000) representing the number of test cases. After that, t test
cases follow. Each of them is presented as follows.
The first line contains one integer n (1 ≤n ≤500 000). The second line contains n integers a1, a2, . . . , an (0 ≤ai ≤
60 for all i).
The sum of n across all test cases in one input file does not exceed 500 000.
Output
For each test case, output the smallest non-negative integer x satisfying the condition above. If there is no such x,
output -1 instead.
Sample Input #1 Sample Output #1
4 13
5 3
3 3 4 1 2 2305843009213693949
3 -1
2 1 2
2
60 60
2
8 0
Explanation for the sample input/output #1
For the first test case, x = 13 satisfies the condition above since (p(13), p(14), p(15), p(16), p(17)) = (3, 3, 4, 1, 2).
It can be shown that there is no non-negative integer smaller than 13 that satisfies the condition above.
ICPC Asia Pacific Championship 2024 Problem C: Bit Counting Sequence
This page is intentionally left blank.
ICPC Asia Pacific Championship 2024 Problem C: Bit Counting Sequence