Alignement de planètes – Épreuve régionale 2020

Niveau 5

Énoncé

Tous les 42 siècles (environ), un alignement absolument parfait des planètes du système P.A.N.D.A se produit. Le prochain va avoir lieu ce dimanche, et avec votre collègue Joseph Marchand vous inventez divers jeux autour de l'événement. Un en particulier attire votre attention.

Supposons que sur chaque planète, un laser soit installé au pôle Nord et tire son faisceau en direction de l'étoile du système P.A.N.D.A. Le but du jeu est de déterminer pour chacune des planètes si le faisceau va atteindre l'étoile, ou bien se heurter à une planète (et si oui, laquelle). On considère que si le laser est tiré d'une planète de rayon $r$, le faisceau ne va se heurter qu'à des planètes de rayon strictement supérieure à $r$.

Après quelques recherches sur la taille respective des planètes, ainsi que de rapides calculs, vous avez résolu le problème pour les 8 planètes du système P.A.N.D.A. Cependant, en tant qu'informaticien assidu, vous vous décidez à généraliser à un système à $N$ planètes, et aimeriez trouver une solution efficace.

Entrée

  • Sur la première ligne un entier $N$ indiquant le nombre de planètes.
  • Sur la deuxième ligne, $N$ entiers séparés par des espaces, représentant le rayon $r_i$ de chaque planète.

Sortie

$N$ entiers précisant pour chaque planète l'indice de la première planète contre laquelle le faisceau se heurte, ou 0 si le faisceau atteint le soleil.

Contraintes

  • $1 ≤ N ≤ 10^6$
  • $1 ≤ r_i ≤ 10^6$

Contraintes d'exécution

Utilisation mémoire maximum
10000 kilo-octets
Temps d'exécution maximum
500 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
5
5 2 4 6 1
Exemple de sortie
0 1 1 0 4
Commentaire

La première et la quatrième planète n'ont aucune contraintes et le laser ira jusqu'à l'étoile. En revanche concernant les autres planètes, le laser heurtera une planète d'un rayon plus important.

Exemple d'entrée
3
2 2 2
Exemple de sortie
0 0 0
Commentaire

Les 3 planètes ont un rayon identique, le laser passera donc sans aucun souci pour les trois planètes jusqu'au soleil.