Alignement de planètes – Regional event 2020

Level 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$

Runtime constraints

Maximum memory usage
10000 kilobytes
Maximum execution time
500 milliseconds

Input/output samples

Sample input
5
5 2 4 6 1
Sample output
0 1 1 0 4
Note

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.

Sample input
3
2 2 2
Sample output
0 0 0
Note

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

Submit your solution

You have to register or log in to be able to submit your solution.