D. Binary String To Subsequences

D. Binary String To Subsequences

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given a binary string ss consisting of nn zeros and ones.

Your task is to divide the given string into the minimum number of subsequences in such a way that each character of the string belongs to exactly one subsequence and each subsequence looks like "010101 ..." or "101010 ..." (i.e. the subsequence should not contain two adjacent zeros or ones).

Recall that a subsequence is a sequence that can be derived from the given sequence by deleting zero or more elements without changing the order of the remaining elements. For example, subsequences of "1011101" are "0", "1", "11111", "0111", "101", "1001", but not "000", "101010" and "11100".

You have to answer tt independent test cases.

Input

The first line of the input contains one integer tt (1≤t≤2⋅1041≤t≤2⋅104) — the number of test cases. Then tt test cases follow.

The first line of the test case contains one integer nn (1≤n≤2⋅1051≤n≤2⋅105) — the length of ss. The second line of the test case contains nn characters '0' and '1' — the string ss.

It is guaranteed that the sum of nn does not exceed 2⋅1052⋅105 (∑n≤2⋅105∑n≤2⋅105).

数据结构英文试卷及答案

application/msword 5星 超过95%的资源 60KB

下载

Output

For each test case, print the answer: in the first line print one integer kk (1≤k≤n1≤k≤n) — the minimum number of subsequences you can divide the string ss to. In the second line print nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤k1≤ai≤k), where aiai is the number of subsequence the ii-th character of ss belongs to.

If there are several answers, you can print any.

Example

input

Copy

4
4
0011
6
111111
5
10101
8
01010000

output

Copy

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 

=========================================================================

贪心的策略当然是能加就加进原本就有的，不能加的时候再重新开辟一个

这里用vector进行模拟，末尾存当前串的编号即可

# include
# include
# include
 
using namespace std;
 
 
 
int ans[200000+10];
 
int main ()
{
 
    //从前往后扫
    //1的话就加进去0,把加进去的0结尾变成1结尾
    //0的话就加1，把加进去的1结尾变成0结尾
    //也就是贪心+模拟，能加就加即可，并不影响后来的
 
    int t;
    cin>>t;
 
    while(t--)
    {
        int n;
        cin>>n;
 
        vector<int>v[2];
 
        string s;
        cin>>s;
 
        s=" "+s;
 
        int now=s[1]-'0';
        int cnt=1;
 
        ans[1]=cnt;
        v[now].push_back(ans[1]);
 
        for(int i=2; i<=n; i++)
        {
 
 
            if(s[i]=='0')
            {
                if(v[1].empty())
                {
                    cnt++;
 
                    ans[i]=cnt;
 
                    v[0].push_back(ans[i]);
                }
                else
                {
                    int now=v[1].back();
                    v[1].pop_back();
                    ans[i]=now;
                    v[0].push_back(ans[i]);
                }
            }
            else
            {
                if(v[0].empty())
                {
                    cnt++;
                    ans[i]=cnt;
 
                    v[1].push_back(ans[i]);
                }
                else
                {
                    int now=v[0].back();
                    v[0].pop_back();
                    ans[i]=now;
                    v[1].push_back(ans[i]);
                }
            }
        }
 
        cout<
        for(int i=1; i<=n; i++)
        {
            cout<" ";
        }
        cout<
 
    }
 
    return  0;
 
}