← 返回题目列表

Codeforces · 1399/D

D. 二进制字符串到子序列

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

给定一个由 $$$n$$$ 零和一组成的二进制字符串 $$$s$$$。

你的任务是将给定的字符串划分为最少数量的子序列,使得字符串的每个字符恰好属于一个子序列,并且每个子序列看起来像“010101 ...”或“101010 ...”(即子序列不应包含两个相邻的零或一)。

回想一下,子序列是可以通过删除零个或多个元素而不改变剩余元素的顺序从给定序列派生的序列。例如,“1011101”的子序列是“0”、“1”、“11111”、“0111”、“101”、“1001”,但不是“000”、“101010”和“11100”。

您必须回答 $$$t$$$ 独立测试用例。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — 测试用例的数量。然后是 $$$t$$$ 测试用例。

测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — $$$s$$$ 的长度。测试用例的第二行包含 $$$n$$$ 字符“0”和“1”——字符串 $$$s$$$。

保证$$$n$$$之和不超过$$$2 \cdot 10^5$$$ ($$$\sum n \le 2 \cdot 10^5$$$)。

输出

对于每个测试用例,打印答案:在第一行打印一个整数 $$$k$$$ ($$$1 \le k \le n$$$) — 您可以将字符串 $$$s$$$ 划分为的最小子序列数。第二行打印 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le k$$$),其中 $$$a_i$$$ 是 $$$s$$$ 的第 $$$i$$$ 个字符所属的子序列号。

如果有多个答案,您可以打印任何答案。

示例

输入 #1

4
4
0011
6
111111
5
10101
8
01010000

输出 #1

2
1 2 2 1 
6
1 2 3 4 5 6 
1
1 1 1 1 1 
4
1 1 1 1 1 2 3 4