Minimizar la Secuencia
Dada una secuencia de
n números , se te pide minimizarla. Una secuencia puede minimizarse de manera lexicográfica al intercambiar dos elementos permitidos de la secuencia. Puedes realizar todos los intercambios que desees. Sin embargo, hay ciertos índices que pueden intercambiarse y otros que no pueden hacerlo entre sí.Comparación lexicográfica de dos secuencias
Una secuencia es lexicográficamente menor que la secuencia si y solo si existe un entero
k (1 ≤ k ≤ n) donde , , …, y . En otras palabras, existe un índice k tal que , mientras que todos los valores anteriores a k son iguales.Dada la matriz de intercambios permitidos, se te pide encontrar la secuencia lexicográficamente más pequeña que se pueda obtener a partir de la secuencia inicial.
Entrada
La primera línea de la entrada contiene un único entero
n (1 ≤ n ≤ 300).La siguiente línea contiene
n enteros separados por espacios (1 ≤ ≤ n) que representan la secuencia inicial, donde todos los números son diferentes.Las siguientes
n líneas contienen n valores 0 o 1 que representan si el intercambio entre dos índices está permitido. Si el valor en la fila i y la columna j es 1, significa que el intercambio entre el i-ésimo y el j-ésimo elementos está permitido. Si el valor es 0, el intercambio no está permitido.Salida
El programa debe imprimir la secuencia lexicográficamente más pequeña que se pueda obtener de la dada.
Ejemplos
Entrada | Salida |
5
4 2 1 5 3
00100
00011
10010
01101
01010 | 1 2 3 4 5 |
7
5 2 4 3 6 7 1
0001001
0000000
0000010
1000001
0000000
0010000
1001000 | 1 2 4 3 6 7 5 |
Explicación
- Podemos realizar los siguientes intercambios:
- ↔ ⇒ 1 2 4 5 3
- ↔ ⇒ 1 2 4 3 5
- ↔ ⇒ 1 2 3 4 5
- ↔ ⇒ 1 2 4 5 3
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB