A16169 | Haunted House
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
You are given a number in binary representation consisting of exactly $n$ bits, possibly, with leading zeroes. For example, for $n = 5$ the number $6$ will be given as $00110$ , and for $n = 4$ the number $9$ will be given as $1001$ .
Let's fix some integer $i$ such that $1 \le i \le n$ . In one operation you can swap any two adjacent bits in the binary representation. Your goal is to find the smallest number of operations you are required to perform to make the number divisible by $2^i$ , or say that it is impossible.
Please note that for each $1 \le i \le n$ you are solving the problem independently.
Let's fix some integer $i$ such that $1 \le i \le n$ . In one operation you can swap any two adjacent bits in the binary representation. Your goal is to find the smallest number of operations you are required to perform to make the number divisible by $2^i$ , or say that it is impossible.
Please note that for each $1 \le i \le n$ you are solving the problem independently.
输入格式
Each test contains multiple test cases. The first line contains the number of test cases $t$ ( $1 \le t \le 10^4$ ). The description of the test cases follows.
The first line of each test case contains one integer $n$ ( $1 \le n \le 10^5$ ) — the length of the binary representation of the number.
The second line of each test case contains a string of length $n$ , consisting of $0$ and $1$ , — the binary representation of the number.
It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$ .
The first line of each test case contains one integer $n$ ( $1 \le n \le 10^5$ ) — the length of the binary representation of the number.
The second line of each test case contains a string of length $n$ , consisting of $0$ and $1$ , — the binary representation of the number.
It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$ .
输出格式
For each test case, for each $1 \le i \le n$ output the smallest number of operations required to make the number divisible by $2^i$ , or output $-1$ if it is impossible.
输入输出样例
输入 #1
6 1 1 2 01 3 010 5 10101 7 0000111 12 001011000110
输出 #1
-1 1 -1 0 1 -1 1 3 -1 -1 -1 3 6 9 12 -1 -1 -1 0 2 4 6 10 15 20 -1 -1 -1 -1 -1
In the first test case, we cannot swap any elements, and the number $1$ is not divisible by $2$ .
In the second test case, the initial number is $1$ . It is not divisible by $2$ , but if we perform the operation, then we obtain the number with binary representation $10$ , which is equal to $2$ in decimal representation, thus, it is divisible by $2$ . But this number is not divisible by $4$ and we cannot obtain any other number using the operations.
In the third test case, the initial number is $2$ . For $i = 1$ we do not have to perform any operations since the initial number is divisible by $2$ . For $i = 2$ we can perform one operation swapping the first two bits (we would obtain $100$ in binary representation, which corresponds to number $4$ ). There is no answer for $i = 3$ .
In the second test case, the initial number is $1$ . It is not divisible by $2$ , but if we perform the operation, then we obtain the number with binary representation $10$ , which is equal to $2$ in decimal representation, thus, it is divisible by $2$ . But this number is not divisible by $4$ and we cannot obtain any other number using the operations.
In the third test case, the initial number is $2$ . For $i = 1$ we do not have to perform any operations since the initial number is divisible by $2$ . For $i = 2$ we can perform one operation swapping the first two bits (we would obtain $100$ in binary representation, which corresponds to number $4$ ). There is no answer for $i = 3$ .
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？
提交通过
评测结果：Accepted