Reverse Sort (Codeforces 1605B)
Tags: Greedy, sortings

Ashish has a binary string $$$s$$$ of length $$$n$$$ that he wants to sort in non-decreasing order.He can perform the following operation:   Choose a subsequence of any length such that its elements are in non-increasing order. Formally, choose any $$$k$$$ such that $$$1 \leq k \leq n$$$ and any sequence of $$$k$$$ indices $$$1 \le i_1 \lt i_2 \lt \ldots \lt i_k \le n$$$ such that $$$s_{i_1} \ge s_{i_2} \ge \ldots \ge s_{i_k}$$$.  Reverse this subsequence in-place. Formally, swap $$$s_{i_1}$$$ with $$$s_{i_k}$$$, swap $$$s_{i_2}$$$ with $$$s_{i_{k-1}}$$$, $$$\ldots$$$ and swap $$$s_{i_{\lfloor k/2 \rfloor}}$$$ with $$$s_{i_{\lceil k/2 \rceil + 1}}$$$ (Here $$$\lfloor x \rfloor$$$ denotes the largest integer not exceeding $$$x$$$, and $$$\lceil x \rceil$$$ denotes the smallest integer not less than $$$x$$$) Find the minimum number of operations required to sort the string in non-decreasing order. It can be proven that it is always possible to sort the given binary string in at most $$$n$$$ operations.

Input: The first line contains a single integer $$$t$$$ $$$(1 \le t \le 1000)$$$  — the number of test cases. The description of the test cases follows.The first line of each test case contains an integer $$$n$$$ $$$(1 \le n \le 1000)$$$  — the length of the binary string $$$s$$$.The second line of each test case contains a binary string $$$s$$$ of length $$$n$$$ containing only $$$0$$$s and $$$1$$$s.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$1000$$$.

Output: For each test case output the following:  The minimum number of operations $$$m$$$ in the first line ($$$0 \le m \le n$$$).  Each of the following $$$m$$$ lines should be of the form: $$$k$$$ $$$i_1$$$ $$$i_2$$$ ... $$$i_{k}$$$, where $$$k$$$ is the length and $$$i_1 \lt i_2 \lt ... \lt i_{k}$$$ are the indices of the chosen subsequence. For them the conditions from the statement must hold. 

Note: In the first test case, the binary string is already sorted in non-decreasing order.In the second test case, we can perform the following operation:   $$$k = 4:$$$ choose the indices $$$\{1, 3, 4, 5\}$$$$$$\underline{1}$$$ $$$0$$$ $$$\underline{1}$$$ $$$\underline{0}$$$ $$$\underline{0}$$$ $$$\rightarrow $$$ $$$\underline{0}$$$ $$$0$$$ $$$\underline{0}$$$ $$$\underline{1}$$$ $$$\underline{1}$$$ In the third test case, we can perform the following operation:  $$$k = 3:$$$ choose the indices $$$\{3, 5, 6\}$$$$$$0$$$ $$$0$$$ $$$\underline{1}$$$ $$$0$$$ $$$\underline{0}$$$ $$$\underline{0}$$$ $$$\rightarrow $$$ $$$0$$$ $$$0$$$ $$$\underline{0}$$$ $$$0$$$ $$$\underline{0}$$$ $$$\underline{1}$$$

Sample Inputs:
3
7
0011111
5
10100
6
001000

Sample Outputs:
0
1
4 1 3 4 5 
1
3 3 5 6

Solution (Python):
for _ in range(int(input())):
    n = int(input())
    s = input()
    bulla = False
    cnt = s.count('1')
    ndx = []
    for i in range(n):
        if s[i] == '1' and i + 1 < n - cnt + 1:
            bulla = True
            ndx.append(i + 1)
    if bulla:
        print(1)
        for i in range(n - 1, n - cnt - 1, -1):
            if s[i] == '0':
                ndx.append(i + 1)
        ndx.sort()
        print(len(ndx), *ndx)
    else:
        print(0)

Solution (Python):
for j in range(int(input())):
    n = int(input())
    s = list(input())
    ss = sorted(s)
    if s == ss:
        print(0)
    else:
        print(1)
        l = [i + 1 for i in range(n) if s[i] != ss[i]]
        print(len(l), *l)

Solution (Python):
for j in range(int(input())):
    n = int(input())
    s = list(input())
    ss = sorted(s)
    if s == ss:
        print(0)
    else:
        print(1)
        l = [i + 1 for i in range(n) if s[i] != ss[i]]
        print(len(l), *l)