Permutation Navale – Épreuve régionale 2024

Énoncé¶

*Njörd — dieu des mers et des océans — est un dieu très organisé. Il aide les humains à positionner leurs bateaux de manière ordonnée.

Pour cela, il fait appel à Freyr — dieu du soleil et de la pluie — pour qu'il pleuve et que les bateaux disposés dans les fjords soient déplacés à leur ville attribuées.

Njörd étant occupé, il demande à Freyr de trouver lui-même comment il pourrait organiser les troupes. C'est pour cela que Freyr fait appel à Jøsëf Marchand afin de trouver la meilleure organisation.*

Freyr fournit à Jøsëf un tableau permutation de $N$ entiers lui permettant de savoir quelles rotations sont possibles sur les bateaux.

Les $N$ bateaux sont représentés par leurs identifiants, un entier unique allant de 1 à $N$. L'ordre initial des bateaux est donnée par un tableau bateaux, contenant les identifiants des bateaux.

Effectuer une rotation signifie déplacer chaque bateau bateaux[i] à la position indiquée par permutation[i]. Freyr peut effectuer autant de rotations qu'il le souhaite.

Une organisation des bateaux est optimale si elle est la plus petite lexicographiquement possible.

Pour rappel, un tableau d'entiers A est lexicographiquement inférieur à un tableau d'entiers B si, pour une certaine position i :

• A et B sont identiques pour tous les éléments avant le i-ème élément ;
• A[i] est inférieur à B[i].

Aidez Freyr à trouver l'organisation optimale des bateaux !

Entrée¶

L’entrée contiendra :

• Sur la première ligne, un entier : N, le nombre de bateaux.
• Sur la ligne suivante, une liste de N entiers séparés par des espaces : permutation, la rotation que Freyr peut effectuer.
• Sur la ligne suivante, une liste de N entiers séparés par des espaces : bateaux, les identifiants de chaque bateau, dans leur ordre initial.

Sortie¶

Afficher, sur une ligne et séparés par un espace, les identifiants des bateaux dans l'ordre optimal que Freyr peut obtenir.

Contraintes¶

• $1 \le N \le 10$

Contraintes de performance¶

• $1 \le N \le 10\,000$