Ordenación mediante desplazamientos#13066
Se te da un arreglo formado por elementos a_1,a_2,...,a_n.
Puedes realizar la siguiente operación varias veces.
Elige un índice
sea el bit encendido más significativo de a_i antes de aplicarle cualquier operación
desplaza cíclicamente hacia la izquierda en los primeros k+1 bits de a_i.
Por ejemplo, si eliges x=4 para desplazar, puedes obtener lo siguiente ¡importante!DP optimizada con mínimos de prefijo sobre estados de desplazamiento cíclico de 18 bits.
Halla el número mínimo de operaciones necesarias para ordenar el arreglo o imprime si es imposible.
La primera línea de cada prueba contiene un único entero (1 \le t \le 10^4) — el número de casos de prueba.
La primera línea de cada caso de prueba contiene un único entero (1 \le n \le 2 \cdot 10^5) — la longitud del arreglo .
La segunda línea de cada caso de prueba contiene enteros a_1 , a_2 , ... , a_n (1 \le a_i \le 2\cdot 10 ^ 5) — el arreglo .
Se garantiza que la suma de sobre todos los casos de prueba no excede 2 \cdot 10^5.
Para cada caso de prueba, imprime un único entero: el número mínimo de operaciones necesarias para ordenar el arreglo .
Ejemplo 1
En el primer caso de prueba, puedes elegir i = 2 y realizar una operación para obtener el arreglo [1 , 1 , 3].
Subtarea ( puntos): \sum n \le 5
Subtarea ( puntos): a_i = 2^x - 1 para todo (1 \le i \le n).
Subtarea ( puntos): a_i \le 3 para todo (1 \le i \le n).
Subtarea ( puntos): Sin restricciones adicionales.