Codeforcess Solution 1605-B B. Reverse Sort ,C++, Java, Js and Python

Algorithm

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 \leq i_{1} < i_{2} < \dots < i_{k} \leq n$ such that $s_{i_{1}} \geq s_{i_{2}} \geq \dots \geq 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}}$ , $\dots$ and swap $s_{i_{⌊ k / 2 ⌋}}$ with $s_{i_{⌈ k / 2 ⌉ + 1}}$ (Here $⌊ x ⌋$ denotes the largest integer not exceeding $x$ , and $⌈ x ⌉$ 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 \leq t \leq 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 \leq n \leq 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 \leq m \leq 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} < i_{2} < . . . < i_{k}$ are the indices of the chosen subsequence. For them the conditions from the statement must hold.

Example
input
Copy
3
7
0011111
5
10100
6
001000
output
Copy
0
1
4 1 3 4 5 
1
3 3 5 6 

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}$ $\to$ $\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}$ $\to$ $0$ $0$ $\underline{0}$ $0$ $\underline{0}$ $\underline{1}$

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include<bits/stdc++.h>
using namespace std;


#define ll long long
#define endl '\n'
#define debug(n) cout<<(n)<<endl;
const ll INF = 2e18 + 99;

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  int t;
  cin>>t;
  while(t--){
    int n;
    cin>>n;
    string s, k;
    cin>>s;
    k = s;
    sort(s.begin(), s.end());
    int arr[n];
    int m = 0;
    for(int i = 0; i < s.length(); i++){
      if(k[i] != s[i]){
        arr[m] = i+1;
        m++;
      }
    }
    if(m != 0){
      cout<<1<<endl;
    }
    cout<<m<<" ";
    for(int i = 0; i < m; i++){
      cout<<arr[i]<<" ";
    }
    cout<<endl;
  }
}

Copy The Code & Try With Live Editor

Input

–

cmd

3
7
0011111
5
10100
6
001000

Output

–

cmd

0
1
4 1 3 4 5
1
3 3 5 6

Demonstration

Codeforcess Solution 1605-B B. Reverse Sort ,C++, Java, Js and Python ,1605-B,Codeforcess Solution

Previous
Codeforces solution 1080-B-B. Margarite and the best present codeforces solution

Next
CodeChef solution DETSCORE - Determine the Score CodeChef solution C,C+

Try With Live Editor

Category - Codeforces Online Judge Maniruzzaman Akash 3 years ago 889 0