Bonjour,

Il y a des mois que je suis resté bloqué en face d'un problème qui demande de trier deux tableaux :

Stocker les niveaux de pollution des différents bacs en attente d'être emportés est utile pour évaluer par exemple la quantité de polluant que vous avez en stock à un moment donné, mais ne conserver que cette valeur pour chaque bac limite ce que vous pouvez faire avec ces données. Impossible de savoir par exemple depuis quand un bac est dans votre stock, ce qu'il contient exactement, etc.

Pour résoudre ce problème, vous avez décidé d'identifier chaque bac par un code numérique. A partir de ce code numérique, vous pourrez ainsi retrouver toutes sortes d'informations sur chaque bac.

Vous avez mis à jour vos données décrivant les niveaux de pollution des bacs, pour y inclure les identifiants des bacs. Il faut maintenant mettre à jour votre programme de tri pour qu'il gère ces identifiants.

LIMITES DE TEMPS ET DE MEMOIRE (Langage : C++)

Temps : 0.5s sur une machine à 1Ghz.
Mémoire : 16000 Ko.

CONTRAINTES

1 <= N <= 20 000, où N est le nombre de bacs décrits dans les données.
0 <= B <= 100 000, où B est le code d'identification d'un bac.
0 <= P <= 108, où P est le niveau de pollution d'un bac.
ENTRÉE

La première ligne de l'entrée contient un entier : le nombre N de bacs décrits dans les données.

Chacune des N lignes suivantes contient deux entiers séparés par un espace : le code d'identification B et le niveau de pollution P d'un bac.

SORTIE

Vous devez afficher N lignes sur la sortie, contenant chacune deux entiers séparés par un espace : le code d'identification et le niveau de pollution d'un bac. Ces lignes donnent les valeurs triées par ordre croissant du niveau de pollution des bacs. Si deux bacs ont le même niveau de pollution, affichez les par ordre croissant de leur code d'identification.

EXEMPLE

entrée :

6
1 6
2 3
4 12
3 7
5 25
7 18
sortie :

2 3
1 6
3 7
4 12
7 18
5 25

bon, j'ai réussi à écrire un code qui affiche correctement mais pour 3 tests, il prend plus que 0.5 s
En fait, j'ai utiliser "sort", "tri rapide", "tri par fusion", mais c'est toujours le 9 ème test qui prend plus que 0.5 s

En fait je ne me maîtrise pas beaucoup le tri par fusion, elle me paraît la plus convenable car sa complexité est minimale, pourriez-vous me donner une partie de la fonction qui fait le tri des deux tableaux en même temps

ca meparrait bizarre que std::sort ne fasse pas l'affaire, quel est ton code?

A noter que sur les spec propose, ce n'est pas etonant. Ici c'est un autre algorithme qu'il faut utiliser.
Tu devrais lire au sujet des algorithmes de tri lineaire.