Minimizzare la Sequenza
Data una sequenza di n numeri , l’obiettivo è minimizzarla. È possibile rendere la sequenza lessicograficamente minima scambiando due elementi ammessi della sequenza. Sei autorizzato a effettuare tutti gli scambi necessari. Tuttavia, non tutte le coppie di indici possono essere scambiate: soltanto alcuni accoppiamenti specificati sono permessi.
Confronto lessicografico di due sequenze
Una sequenza è considerata lessicograficamente più piccola di un’altra sequenza se e solo se esiste un intero k (1 ≤ k ≤ n) tale che , , …, e . In altre parole, esiste un indice k per cui , mentre tutti i numeri precedenti all’indice k sono uguali.
Sulla base della matrice che specifica quali scambi sono ammessi, devi determinare la sequenza lessicograficamente più piccola che si può ottenere a partire da quella iniziale.
Input
La prima riga dell’input contiene un singolo intero n (1 ≤ n ≤ 300).
La riga successiva contiene n interi separati da spazi (1 ≤ ≤ n) che rappresentano la sequenza iniziale, in cui tutti i numeri sono diversi.
Le successive n righe contengono n zeri e uno che indicano se lo scambio tra due indici è ammesso. Se il valore nella riga i e nella colonna j è 1, significa che lo scambio tra gli elementi all’indice i e j è ammesso. Se il valore è 0, lo scambio non è consentito.
Output
Il programma deve stampare la sequenza lessicograficamente più piccola che si può ottenere da quella data.
Esempi
Input | Output |
|---|---|
5 | 1 2 3 4 5 |
7 | 1 2 4 3 6 7 5 |
Spiegazione
Possiamo effettuare i seguenti scambi:
↔⇒ 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