Reorganizar la array dada de modo que todas las posiciones de bits configuradas tengan un valor más alto que otras

Dada una array B1[] y una array binaria B2[] cada una de tamaño N , la tarea es reorganizar la array B1[] de tal manera que para todas las posiciones de setbit i de B2[] el valor de B1[i] será mayor que los valores donde el bit no está establecido en B2[], es decir, para todos (i, j) B1[i] > B1[j] cuando B2[i] = 1, B2[j] = 0 (0 ≤ i, j <N).

Nota: Si es posible realizar varios arreglos, imprima cualquiera de ellos.

Ejemplos:

Entrada: N = 7, B1[] = {1, 2, 3, 4, 5, 6, 7}, B2[] = {0, 1, 0, 1, 0, 1, 0}
Salida: 1 5 2 6 3 7 4
Explicación: Los valores que tienen 1 en la array B2[] son ​​= {2, 4, 6} y los valores con 0 son = {1, 3, 5, 7}.
Entonces, en correspondencia con la array B2[], B1[] se puede reorganizar = {1, 5, 2, 6, 3, 7, 4}
B1[] = {1, 5, 2, 6, 3, 7, 4 }
B2[] = {0, 1, 0, 1, 0, 1, 0}, ahora todos los lugares en B1[i] > B1[j] donde B2[i] = 1 y B2[j] = 0.
También se puede reorganizar como {1, 7, 2, 6, 3, 5, 4}

Entrada: N = 3, B1[] = {4, 3, 5}, B2[] = {1, 1, 1}
Salida: 5 4 3

Planteamiento: El problema se puede resolver a partir de la siguiente idea:

Para organizar B1[] según las posiciones de bit establecidas de B2[], ordene los valores de B1[] y organice los valores más altos en posiciones con bits establecidos y los valores más bajos en posiciones en otras posiciones.

Siga los pasos mencionados a continuación para implementar la idea anterior:

• Haga una lista de pares (digamos v ) con el valor de bit de B2[] y el valor correspondiente en B1[] ,
• Ordene la lista de pares en orden ascendente de valor de bits de B2[] .
• Reorganice B1[] usando el enfoque de dos punteros .
  • Declare el puntero izquierdo con 0 y el puntero derecho con N-1 .
  • Cuando B2[i] es 0 (0 ≤ i < N), establezca B1[] como v[izquierda] e incremente a la izquierda .
  • De lo contrario, establezca B1[i] como v[right] y disminuya a la derecha .
• Devuelve B1[] como respuesta final.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to do required
// operation
void solve(int n, vector<int>& b1, int b2[])
{
    //  Initializing vector of pair
    // to store b2 and b1 array element
    vector<pair<int, int> > v;
 
    int cnt = 1;
    for (int i = 0; i < n; i++) {
 
        // Pushing 1 and 0 integer along with
        // their corresponding element
        // in array b1
        v.push_back({ b2[i], b1[i] });
    }
 
    // Sorting the vector of pair
    // in ascending order
    sort(v.begin(), v.end());
 
    int left = 0, right = n - 1;
 
    // Arranging the array b1
    for (int i = 0; i < n; i++) {
        if (b2[i] == 0)
            b1[i] = v[left++].second;
        else
            b1[i] = v[right--].second;
    }
}
 
// Driver Code
int main()
{
    int N = 3;
    vector<int> B1 = { 3, 4, 5 };
    int B2[] = { 1, 1, 1 };
 
    solve(N, B1, B2);
    for (int x : B1)
        cout << x << " ";
    return 0;
}

// Java program for the above approach
import java.io.*;
import java.util.*;
 
// User defined Pair class
class Pair {
  int x;
  int y;
 
  // Constructor
  public Pair(int x, int y)
  {
    this.x = x;
    this.y = y;
  }
}
 
// class to define user defined conparator
class Compare {
 
  static void compare(Pair arr[], int n)
  {
    // Comparator to sort the pair according to second element
    Arrays.sort(arr, new Comparator<Pair>() {
      @Override public int compare(Pair p1, Pair p2)
      {
        return p1.x - p2.x; // To compare the first element just
        //change the variable from p1.y - p2.y to x.
      }
    });
  }
}
 
class GFG {
 
  // Function to do required
  // operation
  static void solve(int n, int[] b1, int[] b2)
  {
     
    //  Initializing vector of pair
    // to store b2 and b1 array element
    // Array of Pair
    Pair v[] = new Pair[n];
 
    int cnt = 1;
    for (int i = 0; i < n; i++) {
 
      // Pushing 1 and 0 integer along with
      // their corresponding element
      // in array b1
      v[i] = new Pair(b2[i], b1[i]);
    }
 
    // Sorting the vector of pair
    // in ascending order
    Compare obj = new Compare();
    obj.compare(v, n);
 
    int left = 0, right = n - 1;
 
    // Arranging the array b1
    for (int i = 0; i < n; i++) {
      if (b2[i] == 0)
        b1[i] = v[left++].y;
      else
        b1[i] = v[right--].y;
    }
  }
 
  // Driver Code
  public static void main (String[] args) {
    int N = 3;
    int B1[] = { 3, 4, 5 };
    int B2[] = { 1, 1, 1 };
 
    solve(N, B1, B2);
    for (int i = 0; i <B1.length; i++)
      System.out.print(B1[i] + " ");
  }
}
 
// This code is contributed by hrithikgarg03188.

# Python3 program for the above approach
# Function to do required operation
def solve(n, b1, b2):
   
    # Initializing list of pair to store b2 and b1 array element
    v = []
    cnt = 1
    for i in range(n):
        # Pushing 1 and 0 integer along with
        # their corresponding element in array b1
        v.append([b2[i], b1[i]])
     
    v.sort()
    left = 0
    right = n - 1
     
    # Arranging the array b1
    for i in range(n):
        if b2[i] == 0:
            b1[i] = v[left][1]
            left += 1
        else:
            b1[i] = v[right][1]
            right -= 1
             
# Driver Code
N = 3
b1 = [3, 4, 5]
b2 = [1, 1, 1]
solve(N, b1, b2)
for x in b1:
    print(x, end = " ")
''' This code is written by Rajat Kumar (GLA University)'''

// C# program to implement above approach
using System;
using System.Collections.Generic;
 
public class GFG{
 
  class pair : IComparable<pair>
  {
    public int first, second;
    public pair(int first, int second)
    {
      this.first = first;
      this.second = second;
    }
    public int CompareTo(pair b)
    {
      if (this.first != b.first)
        return (this.first < b.first)?-1:1;
      else
        return this.second > b.second?-1:1;
    }
  }
 
 
  static void solve(int n, int[] b1, int[] b2)
  {
    List<pair > v = new List<pair > ();
    for (int i = 0; i < n; i++) {
 
      // Pushing 1 and 0 integer along with
      // their corresponding element
      // in array b1
      v.Add(new pair(b2[i],
                     b1[i]));
    }
 
    // Sorting the vector of pair
    // in ascending order
    v.Sort();
 
    int left = 0, right = n - 1;
 
    // Arranging the array b1
    for (int i = 0; i < n; i++) {
      if (b2[i] == 0)
        b1[i] = v[left++].second;
      else
        b1[i] = v[right--].second;
    }
  }
 
 
  public static void Main (){
 
    // Code
 
    int N = 3;
    int[] B1 = { 3, 4, 5 };
    int[] B2 = { 1, 1, 1 };
 
    solve(N, B1, B2);
    for (int i = B1.Length-1; i >=0 ; i--) 
    { 
      Console.Write(B1[i]);
      Console.Write(" ");
    }  
 
  }
}
 
// This code is contributed by akashish__

<script>
    // JavaScript program for the above approach
 
    // Function to do required
    // operation
    const solve = (n, b1, b2) => {
     
        //  Initializing vector of pair
        // to store b2 and b1 array element
        let v = [];
 
        let cnt = 1;
        for (let i = 0; i < n; i++) {
 
            // Pushing 1 and 0 integer along with
            // their corresponding element
            // in array b1
            v.push([b2[i], b1[i]]);
        }
 
        // Sorting the vector of pair
        // in ascending order
        v.sort();
 
        let left = 0, right = n - 1;
 
        // Arranging the array b1
        for (let i = 0; i < n; i++) {
            if (b2[i] == 0)
                b1[i] = v[left++][1];
            else
                b1[i] = v[right--][1];
        }
    }
 
    // Driver Code
    let N = 3;
    let B1 = [3, 4, 5];
    let B2 = [1, 1, 1];
 
    solve(N, B1, B2);
    for (let x in B1)
        document.write(`${B1[x]} `);
 
    // This code is contributed by rakeshsahni
 
</script>

5 4 3 

Complejidad de tiempo : O(N * logN)
Espacio auxiliar : O(N)