Canvis de rànking U90171

En una competició esportiva, es mantenen classificacions dels jugadors. Cada jugador té un nom únic (un string sense espais) i un rànking (la seva posició a la classificació). Volem detectar els canvis de rànking entre dues classificacions consecutives.

Per exemple, si la primera classificació és:

bobby
millie
poikee
sully
jamie

I la segona classificació és:

jamie
millie
bobby
sully
poikee

Els canvis de rànking són:

• bobby passa de la posició 1 a la 3 (baixa 2 posicions: $-2$)

• jamie passa de la posició 5 a la 1 (puja 4 posicions: $+4$)

• poikee passa de la posició 3 a la 5 (baixa 2 posicions: $-2$)

Observeu que millie i sully no canvien de posició.

Fes un programa que llegeix dues classificacions i mostra els canvis de rànking. Les dues classificacions de l’entrada estan ordenades pel rànking, del primer a l’últim (la posició 1 és la primera línia, la posició 2 és la segona, etc.). La sortida ha d’estar ordenada pel nom dels jugadors, i només cal mostrar els jugadors que han canviat de posició.

Observació

Aquest problema té com a centre d’interès l’eficiència. Feu servir els millors algorismes i estructures de dades que pogueu i considereu que rebreu dades d’entrada de grans dimensions.

En aquest problema és molt important fer servir la funció sort de la llibreria estàndar de C++ (#include <algorithm>), ja que si no es fa servir aquesta, el programa donarà EE, time-limit exceeded.

La meitat dels punts otorgats per la correcció automàtica corresponen a la correctesa del programa, i l’altra meitat a l’eficiència.

Entrada

L’entrada comença amb un enter $n$ ($n \geq 1$) que indica el nombre de jugadors. Després venen $n$ línies amb els noms dels jugadors de la primera classificació, ordenats pel rànking (del primer a l’últim). A continuació, venen altres $n$ línies amb els noms dels jugadors de la segona classificació, també ordenats pel rànking.

Sortida

La sortida són els jugadors que han canviat de posició, ordenats alfabèticament pel nom. Per a cada jugador que ha canviat, s’escriu una línia amb el nom i la diferència de rànking. Si un jugador ha pujat posicions (és a dir, el seu rànking ha millorat, ha passat a un número més petit), la diferència és positiva i es mostra amb un + davant. Si ha baixat posicions, la diferència és negativa.

Si cap jugador ha canviat de posició, s’escriu No hi ha canvis.