Prologin, le concours national d'informatique

Énoncé¶

Les amis se rendent compte que la machine du mathématicien était en fait un encodeur, le même qu’ils ont utilisé lors de la création de la machine ! Ils peuvent donc s’en servir pour aller à l’année qu’ils souhaitent... Cependant, ils confondent l’entrée et la sortie, et se retrouvent à aller dans le mauvais sens. Ne sachant plus du tout en quelle année ils ont atterri, les jeunes sortent de la machine pour tenter de se repérer avant de faire, ils l’espèrent, un bond final vers leur époque d’origine.

Les jeunes arrivent coincés dans une grotte, qui menace de s’effondrer à cause de l’apparition soudaine de la machine. Plusieurs reliques se trouvent délaissées dans la grotte, et récupérer une relique avant une autre de manière sûre ne peut se faire que sous certaines conditions. Il faut aider les amis à récupérer toutes les reliques avant de re-rentrer dans la machine.

La grotte contient $N$ reliques et chaque relique possède une masse $M$. Pour aller d'une relique $i$ à une relique $j$, il faut respecter la relation :

$i \oplus M_j \leq j \oplus M_i$,

où $\oplus$ représente le Ou Exclusif binaire. Par exemple :

$3 \oplus 6 = (011)_2 \oplus (110)_2 = (101)_2 = 5$

Il faut alors trouver un ordre dans lequel nos amis peuvent prendre les reliques sans faire s'effondrer la grotte.

Note : Nos amis ne peuvent pas revenir sur une relique une fois prise, cela fera s'effondrer la grotte.

Entrée¶

L’entrée contiendra :

Sur la première ligne, un entier : N, le nombre de reliques.
Sur la ligne suivante, une liste de N entiers séparés par des espaces : M, la masse de chaque relique.

Sortie¶

Afficher, sur une ligne et séparés par un espace, N entiers : la liste des positions indiquant l'ordre dans lequel il faut récupérer les reliques. S'il existe plusieurs solutions, affiche n'importe laquelle d'entre elles.

Contraintes¶

$2 \le N \le 10$
$1 \le M_i \le 100\,000$

Contraintes de performance¶

$2 \le N \le 100\,000$

Contraintes d'exécution

Utilisation mémoire maximum: 100000 kilo-octets
Temps d'exécution maximum: 1000 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée

5
5 4 3 2 1

Exemple de sortie

1 2 3 4 5

Commentaire

Il est possible d'aller de :

la relique 1 à la relique 2 ($1 \oplus 4 < 2 \oplus 5$ soit $5 \le 7$)
la relique 1 à la relique 3 ($1 \oplus 3 < 3 \oplus 5$ soit $2 \le 6$)
la relique 1 à la relique 5, et inversement ($1 \oplus 5 = 5 \oplus 1$ soit $4 \le 4$)
la relique 2 à la relique 3 ($2 \oplus 3 < 3 \oplus 4$ soit $1 \le 7$)
la relique 2 à la relique 4, et inversement ($2 \oplus 4 = 4 \oplus 2$ soit $6 \le 6$)
la relique 3 à la relique 4 ($3 \oplus 2 < 4 \oplus 3$ soit $1 \le 7$)
la relique 3 à la relique 5 ($3 \oplus 1 < 5 \oplus 3$ soit $2 \le 6$)
la relique 4 à la relique 1 ($4 \oplus 5 < 1 \oplus 2$ soit $1 \le 3$)
la relique 4 à la relique 5 ($4 \oplus 1 < 5 \oplus 2$ soit $5 \le 7$)
la relique 5 à la relique 2 ($5 \oplus 4 < 2 \oplus 1$ soit $1 \le 3$)

Graphe

Cette image montre sous la forme d'un graphe orienté les reliques possibles à prendre.

Il est donc possible de récupérer la totalité des reliques, par exemple en prenant tout d'abord la relique $1$, puis la relique $2$, puis la relique $3$, puis la relique $4$ et enfin la relique $5$.

Notez qu'il existe plusieurs autres solutions, comme par exemple $5, 1, 3, 4, 2$.