Suma vs MEX#13063
Se te da un número entero . Una permutación de elementos se llama buena si se cumple la siguiente condición:
para cada índice (1 \le i \le n) : \sum\limits_{j=1}^{i} p_j es divisible entre (p_1 , p_2 , \ldots, p_i).
donde es el menor entero positivo que no está presente en el arreglo maximiza la permutación usando algún proceso parecido a la memorización.
Encuentra una permutación buena de elementos o informa que es imposible.
La primera línea contiene un único entero (1 \le t \le 700)— la cantidad 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 de la permutación.
Se garantiza que la suma de sobre todos los casos de prueba no excede 2 \cdot 10^5.
Para cada caso de prueba, imprime si existe una permutación buena y luego imprime una permutación buena de elementos, o imprime si no existe ninguna permutación buena.
Ejemplo 1
En el tercer caso de prueba p = [3,1,4,2] funciona porque
Cuando i = 1 , p_1 = 3 , \text{MEX}(3) = 1 y 3 \bmod 1= 0 , por lo tanto es válido.
Cuando i = 2 , p_1 + p_2 = 4 , \text{MEX}(3 , 1) = 2 y 4 \bmod 2=0 , por lo tanto es válido.
Cuando i = 3 , p_1 + p_2 + p_3 = 8 , \text{MEX}(3 , 1 , 4) = 2 y 8 \bmod 2=0 , por lo tanto es válido.
Cuando i = 4 , p_1 + p_2 + p_3 + p_4 = 10 , \text{MEX}(3,1,4,2) = 5 y 10 \bmod 5=0 , por lo tanto es válido.
Por lo tanto, la permutación es una construcción válida.
Subtarea ( puntos): \sum n \le 10.
Subtarea ( puntos): Sin restricciones adicionales.