ABC113-C

解けた。

考えたこと

1. 都市番号と誕生年をリストに順番にいれる
2. 同時に辞書に都市番号をキーとして誕生年をリストで入れる
3. 辞書の中の各都市番号の誕生年リストをソートする
4. 全部おわったら、都市番号と誕生年のリストを頭から見ていき、都市番号については辞書に都市番号を渡して得られるリストにindexで誕生順を得る
5. zfill()でゼロで埋めて出力
6. TLE。indexはおそらく線形探索なので遅いと考える
7. 線形探索から二分探索に変更し無事AC

面倒だが難しくはなかった。実行時間が気になるが、ほかのAC回答も大差ない実行時間なので、pythonだとこの辺りが普通なのか？

atcoder.jp