Problem:


Score: 300 points

Problem Statement

In Republic of Atcoder, there are N prefectures, and a total of M cities that belong to those prefectures.

City i is established in year Y_i and belongs to Prefecture P_i.

You can assume that there are no multiple cities that are established in the same year.

It is decided to allocate a 12-digit ID number to each city.

If City i is the x-th established city among the cities that belong to Prefecture i, the first six digits of the ID number of City i is P_i, and the last six digits of the ID number is x.

Here, if P_i or x (or both) has less than six digits, zeros are added to the left until it has six digits.

Find the ID numbers for all the cities.

Note that there can be a prefecture with no cities.

Constraints

1 \leq N \leq 10^5

1 \leq M \leq 10^5

1 \leq P_i \leq N

1 \leq Y_i \leq 10^9

Y_i are all different.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
P_1 Y_1
:
P_M Y_M

Output

Print the ID numbers for all the cities, in ascending order of indices (City 1, City 2, ...).

Sample Input 1

2 3
1 32
2 63
1 12

Sample Output 1

000001000002
000002000001
000001000001

As City 1 is the second established city among the cities that belong to Prefecture 1, its ID number is 000001000002.

As City 2 is the first established city among the cities that belong to Prefecture 2, its ID number is 000002000001.

As City 3 is the first established city among the cities that belong to Prefecture 1, its ID number is 000001000001.

Sample Input 2

2 3
2 55
2 77
2 99

Sample Output 2

000002000001
000002000002
000002000003



Sample input:
2 3
1 32
2 63
1 12


Sample output:
000001000002
000002000001
000001000001

Submission status: Accepted

Solution code:
# 入力
N, M = map(int, input().split())
P = [0] * M
Y = [0] * M
city_list = []
for i in range(M):
    P[i], Y[i] = map(int, input().split())
    city_list.append([i, P[i], Y[i]])

# YでソートしてPでソートして識別番号つけて市番号出力
# Yでソート
city_list = sorted(city_list, key=lambda x: x[2])

# Pでソート
city_list = sorted(city_list, key=lambda x: x[1])

# 識別番号つける
# 県が同じうちは下6桁はインクリメント
city_number = [""] * M
city_count_in_prefecture = 1
for i in range(M):
    if i == 0:  # 一番最初ならば
        city_number[city_list[i][0]] = str(city_list[i][1]).zfill(6) + str(city_count_in_prefecture).zfill(6)
    elif city_list[i][1] == city_list[i - 1][1]:  # 前の市の県と同じならば
        city_count_in_prefecture += 1
        city_number[city_list[i][0]] = str(city_list[i][1]).zfill(6) + str(city_count_in_prefecture).zfill(6)
    else:  # 前の市の県と違うならば
        city_count_in_prefecture = 1
        city_number[city_list[i][0]] = str(city_list[i][1]).zfill(6) + str(city_count_in_prefecture).zfill(6)

# 市番号出力
for i in range(M):
    print(city_number[i])

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
city_list = []
for i in range(M):
    a,b = map(int,input().split())
    city_list.append([a,b,0,i])

city_list.sort(key=lambda city_list:city_list[1])
city_list.sort(key=lambda city_list:city_list[0])

city_id = 1
city_cnt = 1
i = 0

while True:
    if i + 1 > M:
        break

    elif city_id == city_list[i][0]:
        city_list[i][2] = city_cnt
        city_cnt += 1
        i += 1
    
    elif city_id <= N+1:
        city_cnt = 1
        city_id += 1

    else:
        break
            
city_list.sort(key=lambda city_list:city_list[3])

for city in city_list:
    print('{:0>6}{:0>6}'.format(city[0],city[2]))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
p = []
for i in range(m):
    p1= list(map(int,input().split()))
    p.append(p1 + [i])
p2 = sorted(p,key=lambda x:(x[0],x[1]))
p3 = []
pref = 0
state = 0
for j in p2:
    if j[0] != pref:
        pref = j[0]
        state = 1
        p3.append([j[0],j[1],j[2],str(j[0]).rjust(6, '0')+str(state).rjust(6,'0')])
    else:
        state += 1
        p3.append([j[0],j[1],j[2],str(j[0]).rjust(6, '0')+str(state).rjust(6,'0')])
p3.sort(key = lambda x:(x[2]))
for i in p3:
    print(i[3])

Submission status: Accepted

Solution code:
N, M = [int(_) for _ in input().split()]
PY = [[int(_) for _ in input().split()] + [_] for _ in range(M)]
# 2番目のKeyでソート
PY.sort(key = lambda x : x[1])
# 順番カウント用
cnt = [0] * (N + 1)
ans = [""] * M

for p, y, i in PY:
    # 何番目かカウント
    cnt[p] += 1
    # 答え
    ans[i] = str(p).zfill(6) + str(cnt[p]).zfill(6)

print("\n".join(ans))

Submission status: Accepted

Solution code:
import bisect
from collections import defaultdict
import sys
input = sys.stdin.readline
n,m=map(int,input().split())
C=[]
D=defaultdict(list)
for i in range(m):
  p,y=map(int,input().split())
  C.append([p,y])
  D[p].append(y)
for k in D.keys():
  D[k].sort()
for i in range(m):
  y=bisect.bisect_left(D[C[i][0]],C[i][1])+1
  print(str(C[i][0]).zfill(6)+str(y).zfill(6))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
PY = [[i,0] + list(map(int, input().split())) for i in range(M)]
# [index, nth city, pref num, birth year]

PY.sort(key=lambda x:(x[2],x[3]))

p = -1
num = 1
for i,py in enumerate(PY):
  if p != py[2]:
    p = py[2]
    num = 1
    PY[i][1] = num
  else:
    num += 1
    PY[i][1] = num

PY.sort(key=lambda x:x[0])

for py in PY:
  print('{:0=6}{:0=6}'.format(py[2], py[1]))

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
D = dict()
A = []
for i in range(m):
    p,y = map(int,input().split())
    A.append([p,y,i,0])
A.sort(key = lambda x:x[1])
for a in A:
    if a[0] not in D:
        D[a[0]] = 1
    else:
        D[a[0]] +=1
    a[3] = D[a[0]]
A.sort(key = lambda x:x[2])
for a in A:
    print(str(a[0]).zfill(6)+str(a[3]).zfill(6))

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
PY = [list(map(int,input().split())) for i in range(M)]

PY_copy = [PY[i] + [i] for i in range(M)]
PY_copy = sorted(PY_copy, key=lambda x:(x[0],x[1]))

order = 0
previous_prefecture = PY_copy[0][0]
for i in range(M):
  if PY_copy[i][0] == previous_prefecture:
    order += 1
  else:
    previous_prefecture = PY_copy[i][0]
    order = 1
  PY_copy[i] = PY_copy[i] + [order]

PY_copy = sorted(PY_copy, key=lambda x:x[2])
## PY_copy = [P, Y, index, dict_order]

for i in range(M):
  P_zfill = str(PY_copy[i][0]).zfill(6)
  order_zfill = str(PY_copy[i][3]).zfill(6)
  print(P_zfill + order_zfill)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
city=list(list(map(int,input().split()))+[i] for i in range(m))
city.sort(key=lambda x:x[1])
city.sort(key=lambda x:x[0])
for j,l in enumerate(city):
    if j!=0 and city[j-1][0]==city[j][0]:
        city[j].append(city[j-1][3]+1)
    elif j!=0 and city[j-1][0]!=city[j][0]:
        city[j].append(1)
    else:
        city[j].append(1)
city.sort(key=lambda x:x[2])
for k in range(m):
    print('{0:06d}{1:06d}'.format(city[k][0],city[k][3]))

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
PY=list(list(map(int,input().split()))+[i] for i in range(M))
PY.sort(key=lambda x:x[1])
PY.sort(key=lambda x:x[0])
for j,J in enumerate(PY):
    if j!=0 and PY[j-1][0]==PY[j][0]:
        PY[j].append(PY[j-1][3]+1)
    elif j!=0 and PY[j-1][0]!=PY[j][0]:
        PY[j].append(1)
    else:
        PY[j].append(1)
PY.sort(key=lambda x :x[2])
for k in range(M):
    print('{0:06d}{1:06d}'.format(PY[k][0],PY[k][3]))

Submission status: Accepted

Solution code:
import bisect

n, m = map(int, input().split())

pn_cn = []
pn_cn_dict = {}


for _ in range(m):
    pn, cn = map(int, input().split())
    cities = pn_cn_dict.get(pn)
    if cities is None:
        cities = [cn]
    else:
        cities.append(cn)
    pn_cn_dict[pn] = cities
    pn_cn.append((pn, cn))

for k in pn_cn_dict:
    c = pn_cn_dict[k]
    c = sorted(c)
    pn_cn_dict[k] = c

for pn, cn in pn_cn:
    ci = bisect.bisect(pn_cn_dict[pn], cn)
    print("{:06}{:06}".format(pn, ci))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
birth_list = []
for i in range(M):
    Pi, Yi = map(int, input().split())
    birth_list.append([Pi, Yi])

counter = -1
prev_pref = -1
for city in sorted(birth_list, key=lambda x: (x[0], x[1])):
    # print(city)
    if city[0] != prev_pref:
        counter = 1
    else:
        counter += 1
    identity_number = str(city[0]).zfill(6) + str(counter).zfill(6)
    city.append(identity_number)
    prev_pref = city[0]

for city in birth_list:
    print(city[2])

Submission status: Accepted

Solution code:
N, M = map(int,input().split())

PY = [[0]*4]*M
p_dict = {}
for i in range(M):
    p, y = map(int,input().split())
    
    if p not in p_dict.keys():
        p_dict[p] = [[p, y, i]]
    else:
        p_dict[p].append([p, y, i])

ans = []
for p in p_dict.keys():
    p_dict[p].sort()
    for i in range(len(p_dict[p])):
        ans.append(p_dict[p][i] + [i+1])
 
ans.sort(key=lambda x: x[2])

for i in range(M):
    print("{:06d}{:06d}".format(ans[i][0], ans[i][3]))

Submission status: Accepted

Solution code:

N, M = map(int,input().split())

PY = [[0]*4]*M
p_dict = {}
for i in range(M):
    p, y = map(int,input().split())
    
    if p not in p_dict.keys():
        p_dict[p] = [[p, y, i]]
    else:
        p_dict[p].append([p, y, i])

ans = []
for p in p_dict.keys():
    p_dict[p].sort()
    for i in range(len(p_dict[p])):
        ans.append(p_dict[p][i] + [i+1])
 
ans.sort(key=lambda x: x[2])

for i in range(M):
    print("{:06d}{:06d}".format(ans[i][0], ans[i][3]))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
List = [list(map(int, input().split())) for i in range(M)]

ans = [' ']*M
num = [1]*N

for i, v in sorted(enumerate(List), key=lambda x: (x[1][0], x[1][1])):
    ans[i] = '{:06}{:06}'.format(v[0], num[v[0]-1])
    num[v[0]-1] += 1
    
print('\n'.join(ans))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
py = [[i] + list(map(int, input().split())) for i in range(m)]
py.sort(key=lambda x:(x[1],x[2]))

city = py[0][1]
num = 0

for i in py:
    if i[1] == city:
        num += 1
    else:
        num = 1
        city = i[1]
    i.append(num)

py.sort(key=lambda x:[x[0]])

for i in py:
    print('{:06}{:06}'.format(i[1], i[3]))

Submission status: Accepted

Solution code:
"""



"""

N, M = map(int, input().split())
#cityの番号を付与して、格納
city = [list(map(int, input().split())) + [i] + [0] for i in range(M)]

city.sort(key=lambda x: (x[0], x[1]))

for m in range(M):
    if m == 0:
        city[m][3] = 1
    elif city[m][0] != city[m - 1][0]:
        city[m][3] = 1
    else:
        city[m][3] = city[m - 1][3] + 1

city.sort(key=lambda x: x[2])

for m in range(M):
    print(str(city[m][0]).zfill(6) + str(city[m][3]).zfill(6))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
py = [[i] + list(map(int, input().split())) for i in range(m)]
py.sort(key=lambda x:(x[1], x[2]))

city = py[0][1]
num = 0

for i in py:
    if i[1] == city:
        num += 1
    else:
        num = 1
        city = i[1]
    i.append(num)

py.sort()

for i in py:
    print('{:06}{:06}'.format(i[1], i[3]))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
py = [[i] + list(map(int, input().split())) for i in range(m)]
py.sort(key=lambda x:(x[1],x[2]))

city = py[0][1]
num = 0

for i in py:
    if i[1] == city:
        num += 1
    else:
        city = i[1]
        num = 1
    i.append(num)

py.sort()

for i in py:
    print('{:06}{:06}'.format(i[1], i[3]))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
PY = [list(map(int, input().split() +[x])) for x in range(M)]

PY = sorted(PY)

keyP = -1
for i, (P, Y, _) in enumerate(PY):
  if keyP != P:
    keyP = P
    keyNo = 1

  PY[i].append("{:0>6}{:0>6}".format(keyP, keyNo))
  keyNo += 1

for P, Y, _, s in sorted(PY, key=lambda x:x[2]):
  print(s)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(M)]
ans = [''] * M
num = [1] * N

for i, v in sorted(enumerate(X), key=lambda x: (x[1][0], x[1][1])):
    ans[i] = '{:06}{:06}'.format(v[0], num[v[0] - 1])
    num[v[0] - 1] += 1
    
print('\n'.join(ans))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
X = [[i] + list(map(int, input().split())) for i in range(M)]
X.sort(key=lambda x: (x[1], x[2]))

city = X[0][1]
num = 0
for v in X:
    if city == v[1]:
        num += 1
    else:
        city = v[1]
        num = 1
    v.append(num)

X.sort()
for v in X:
    print('{:06}{:06}'.format(v[1], v[3]))

Submission status: Accepted

Solution code:
from __future__ import print_function
# import numpy as np
import sys
import math,string,itertools,fractions,heapq,collections,re,array,bisect,copy,functools
import heapq
from heapq import heappush
from heapq import heappop
import random


def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)

n,m = map(int, input().split())
p=[i for i in range(m+1)]
y=[i for i in range(m+1)]
for i in range(1,m+1):
    p[i],y[i] = map(int, input().split())


l_pref=[[] for _ in range(n+1)]    # 県の数(==n)だけ空リストを用意
for i in range(1,m+1):
    l_pref[p[i]].append((y[i],i))
for i in range(1,n+1):
    l_pref[i].sort()

# eprint(l_pref)


lll = [(1,1) for i in range(m+1)]
for i in range(1,n+1):
    for j in range(len(l_pref[i])):
        lll[l_pref[i][j][1]] = j+1
# eprint(lll)

for i in range(1,m+1):
    # temp =  l_pref[p[i]].index((y[i],i))  + 1
    print("0"*(6-len(str(p[i])))  +  str(p[i])  +  "0"*(6-len(str(lll[i]))) + str(lll[i]) )

Submission status: Accepted

Solution code:
import sys
rr = lambda: sys.stdin.readline().strip()
ri = lambda: int(rr())
rs = lambda: [int(_) for _ in rr().split()]

from operator import itemgetter

N, M = rs()
data = [[i]+[int(_) for _ in input().split()] for i in range(M)]

data.sort(key=itemgetter(1, 2))
ans = [''] * M

P = -1
cnt = 0
for d in data:
    if P != d[1]:
        P = d[1]
        cnt = 1
    else:
        cnt += 1
    ans[d[0]] = str(P).zfill(6) + str(cnt).zfill(6)

for i in range(M):
    print(ans[i])

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
Y = [[] for _ in range(n)]
for i in range(m):
    p,yi = map(int, input().split())
    Y[p-1].append((yi,i))
ans = [-1 for _ in range(m)]
for i,d in enumerate(Y):
    d.sort()
    for k,(a,b) in enumerate(d):
        ans[b] = str(i+1).rjust(6,"0") + str(k+1).rjust(6,"0")
for i in range(m):
    print(ans[i])

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
Y = [[] for _ in range(n)]
for i in range(m):
    p,yi = map(int, input().split())
    Y[p-1].append((yi,i))
ans = [-1 for _ in range(m)]
for i,d in enumerate(Y):
    d.sort()
    for k,(a,b) in enumerate(d):
        ans[b] = str(i+1).rjust(6,"0") + str(k+1).rjust(6,"0")
print(*ans, sep = "\n")

Submission status: Accepted

Solution code:
class City:
  def __init__(self, born):
    self.born = born
    self.id = ''

class Pref:
  def __init__(self, id):
    self.id = str(id).zfill(6)
    self.cities = []
  
  def add_city(self, city):
    self.cities.append(city)
  
  def issue_ids(self):
    self.cities.sort(key=lambda c:c.born)
    for i, c in enumerate(self.cities):
      c.id = self.id + str(i+1).zfill(6)

      
prefs = dict()
cities = []
n, m = map(int, input().split())
for _ in range(m):
  p, y = map(int, input().split())
  city = City(y)
  cities.append(city)
  if p in prefs:
    prefs[p].add_city(city)
  else:
    pref = Pref(p)
    pref.add_city(city)
    prefs[p] = pref

for p in prefs.values():
  p.issue_ids()

for c in cities:
  print(c.id)

Submission status: Accepted

Solution code:
N, M = [int(x) for x in input().split()]

PY = []

Px = [0] * (N+1)
for i in range(M):
    p, y = [int(x) for x in input().split()]
    PY.append((i, p, y))

PY.sort(key=lambda x:x[2])
result = [None]*M
for i, p, y in PY:
    Px[p]+=1
    result[i] = "%06d%06d" % (p, Px[p])

for x in result:
    print(x)

# 2 3
# 1 32
# 2 63
# 1 12

# 000001000002
# 000002000001
# 000001000001

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import itertools


def solve(N: int, M: int, P: "List[int]", Y: "List[int]"):

    L = []
    R = [""] * M
    for p,y,i in zip(P,Y,range(M)):
        L.append((i,p,y))
    L.sort(key=lambda x: x[1]*10**10+x[2])

    for k,g in itertools.groupby(L,key=lambda x: x[1]):
        for i,gg in enumerate(g):
            R[gg[0]] = str(gg[1]).zfill(6) + str(i+1).zfill(6)

    for r in R:
        print(r)




# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    P = [int()] * (M)  # type: "List[int]" 
    Y = [int()] * (M)  # type: "List[int]" 
    for i in range(M):
        P[i] = int(next(tokens))
        Y[i] = int(next(tokens))
    solve(N, M, P, Y)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m = list(map(int,input().split()))

p = [0]*(m)
y = [0]*(m)

for i in range(0,m):
    p[i],y[i] = list(map(int,input().split()))

b = [[p[i],y[i]] for i in range(0,m)]

a = sorted(b)
num = {}
count = 1
num[a[0][1]] = 1

for i in range(1,m):
    if a[i-1][0] == a[i][0]:
        count += 1
    else:
        count = 1    
    num[a[i][1]] = count

for i in range(0,m):
    z1 = 6 - len(str(b[i][0]))
    z2 = 6 - len(str(num[b[i][1]]))
    print("0"*z1 + str(b[i][0]) + "0"*z2 + str(num[b[i][1]]))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

import collections, bisect

n, m = map(int, input().split())
p = [[int(j) for j in input().split()] for i in range(m)]
a = collections.defaultdict(list)
for x, y in sorted(p):
  a[x] += [y]
for x, y in p:
  z = bisect.bisect(a[x], y)
  print("%06d%06d"%(x,z))

Submission status: Accepted

Solution code:
from operator import itemgetter

n, m = map(int, input().split())
ans = []

for i in range(m):
    p, y = map(int, input().split())
    ans.append((i, p, y))

ans = sorted(ans, key=itemgetter(1, 2))

_city = -1
for i in range(len(ans)):
    if _city != ans[i][1]:
        cnt_city = 1
        _city = ans[i][1]
    else:
        cnt_city += 1
    ans[i] += (cnt_city,)

ans.sort()

for _ans in ans:
    print(str(_ans[1]).zfill(6)+str(_ans[3]).zfill(6))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
C - ID
https://atcoder.jp/contests/abc113/tasks/abc113_c

"""
import sys

from collections import defaultdict
from bisect import bisect_left

def solve(N, M, cities):
    res = defaultdict(list)
    for p, y in cities:
        res[p].append(y)
    for k in res.keys():
        res[k].sort()
    return ['{:06d}{:06d}'.format(p, bisect_left(res[p], y) + 1) for p, y in cities]


def main(args):
    N, M = map(int, input().split())
    cities = [[int(i) for i in input().split()] for i in range(M)]
    ans = solve(N, M, cities)
    print(*ans, sep='\n')


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
l=[]
for i in range(m):
    a=list(map(int,input().split()))
    a.append(i)
    l.append(a)
l.sort(key=lambda x:x[1])
l.sort(key=lambda x:x[0])
j,y=0,1
for i in range(m):
    x=l[i].pop(0)
    y=y+1 if j==x else 1
    j=x
    l[i][0]=str(x).zfill(6)+str(y).zfill(6)
l.sort(key=lambda x:x[1])
for i in l:print(i[0])

Submission status: Accepted

Solution code:
N,M = map(int,input().split())

ypi = []

for i in range(M):
    p, y = map(int,input().split())
    ypi.append([y, p, i])

ypi.sort()

rank = [0] * N

ans = [''] * M
for count in range(M):
    y, p, i = ypi[count]
    rank[p-1] += 1
    ans[i] = '{:06}'.format(p)+'{:06}'.format(rank[p-1])

for s in ans:
    print(s)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
PY=[]
for i in range(m):
    p,y=map(int,input().split())
    PY.append([y,p,i])
PY.sort()

pre=[0]*n
citys=['']*m
for y,p,i in PY:
    pre[p-1]+=1
    citys[i]=str(p).zfill(6)+str(pre[p-1]).zfill(6)
for city in citys:
    print(city)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
PY = [list(map(int, input().split())) for _ in range(M)]

cs = {}
for p, y in PY:
	if not p in cs:
		cs[p] = [y]
	else:
		cs[p] += [y]

csm = {}
for k, v in cs.items():
	v.sort()
	csm[k] = {}
	for i, p in enumerate(v):
		csm[k][p] = i + 1

for p, y in PY:
	print("{:06d}{:06d}".format(p, csm[p][y]))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
P = []
Y = []
for i in range(M):
    p, y = map(int, input().split())
    P.append(p)
    Y.append(y)


pref_map = {}
for i in range(1, N+1):
    pref_map[i] = []

for i in range(M):
    pref_map[P[i]].append([i, Y[i]])


city_list = []
for k in pref_map.keys():
    pref_map[k].sort(key=lambda x: x[1])
    idx = 1
    for c in pref_map[k]:
        city_list.append([c[0], k, idx])
        idx += 1

city_list.sort(key=lambda x:x[0])

for city in city_list:
    print(format(city[1], '06d') + format(city[2], '06d'))

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
all_city = [list(map(int,input().split())) for i in range(M)]
 
city = {}
for i in all_city:
    if i[0] in city:
        city[i[0]].append(i[1])
    else:
        city[i[0]] = [i[1]]
 
under6 = {}
for i,k in city.items():
    city[i] = sorted(k)
    for j in range(len(city[i])):
        under6[city[i][j]] = j + 1

def change_Prefecture_code(prefecture):
    return str(prefecture).zfill(6)
 
def change_birth_code(birth_num):
    return str(birth_num).zfill(6)
 
for i in all_city:
    print(change_Prefecture_code(i[0]) + change_birth_code(under6[i[1]]))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from operator import itemgetter

N, M = list(map(int, input().split()))
A = [[0] * 4 for i in range(M)]
for i in range(M):
    A[i][0], A[i][1] = list(map(int, input().split()))
    A[i][2] = i

sorted_A = sorted(A, key=itemgetter(1))

P_num = [1]*N
for a in sorted_A:
    y = a[0]
    a[3] = P_num[y-1]
    P_num[y-1] += 1

B = sorted(sorted_A, key=itemgetter(2))
for b in B:
    print("%06d%06d" % (b[0], b[3]))

Submission status: Accepted

Solution code:
def mks(num):
  s=str(num)
  if len(s)<6:
    s='0'*(6-len(s))+s
  return s

n,m=map(int,input().split())
arr=[]
for i in range(m):
  p,y=map(int,input().split())
  arr.append([p,y,i])
ans=[0]*m
arr=sorted(arr,key=lambda x:x[1])
arr=sorted(arr,key=lambda x:x[0])
tmp=arr[0][0]
cnt=1
for i in range(m):
  if arr[i][0]==tmp:
    s1,s2=mks(tmp),mks(cnt)
    ans[arr[i][2]]=s1+s2
    cnt+=1
  else:
    cnt=1
    tmp=arr[i][0]
    s1,s2=mks(tmp),mks(cnt)
    ans[arr[i][2]]=s1+s2
    cnt+=1
for i in range(m):
  print(ans[i])

Submission status: Accepted

Solution code:
N,M = [ int(it) for it in input().split() ]
li = [ [i,[ int(it) for it in input().split() ]] for i in range(M) ]
li = [ (it[0],it[1][0],it[1][1]) for it in li]

sor = [ [] for i in range(N+1) ]
for i,p,y in li:
  sor[p].append((i,y))
[ it.sort(key = lambda x:x[1]) for it in sor]

coo = [0]*M
for so in sor:
  for j in range(len(so)):
    i,y = so[j]
    coo[i] = j+1
for i in range(M):
  print ( "{0:06d}{1:06d}".format(li[i][1], coo[i]) )

Submission status: Accepted

Solution code:
from operator import itemgetter
n,m=map(int,input().split())
l=[]
id_list=[]
for i in range(m):
  obj = list(map(int, input().split()))
  obj.append(i+1)
  l.append(obj)
l=sorted(l, key=itemgetter(0,1))
idx=0
for j in range(m):
  id_obj=[]
  if j == 0:
    idx=1
  else:

    if l[j][0] == l[j-1][0]:
      idx+=1
    else:
      idx =1
  id_obj.append(l[j][2])
  id_obj.append(str(l[j][0]).zfill(6)+str(idx).zfill(6))
  id_list.append(id_obj)
id_list = sorted(id_list)
for k in range(m):
  print(id_list[k][1])

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
kv = {}
lst = []
for _ in range(M):
    x, y = map(int, input().split())
    lst.append("{0} {1}".format(x, y))
    if x in kv:
        kv[x][y] = 1
    else:
        kv[x] = {y:1}

for k1 in sorted(kv.keys()):
    keys = sorted(kv[k1].keys())
    for idx, k2 in enumerate(keys, 1):
        kv[k1][k2] = idx

for s in lst:
    x, y = map(int, s.split())
    print("{0:06d}{1:06d}".format(x,kv[x][y]))

Submission status: Accepted

Solution code:
from collections import namedtuple, defaultdict

City = namedtuple('City', ('num', 'pref', 'year'))
cities = defaultdict(list)

n, m = map(int, input().split())
for i in range(m):
    p, y = map(int, input().split())
    cities[p].append(City(i, p, y))

for _, cs in cities.items():
    cs.sort(key=lambda c: c.year)

ids = ['' for _ in range(m)]
for pref, cs in cities.items():
    for ith, c in enumerate(cs):
        ids[c.num] = str(c.pref).zfill(6) + str(ith + 1).zfill(6)

for id in ids:
    print(id)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

N, M = [int(x) for x in input().split()]
P_Y_li = []
for _ in range(M):
    P_Y_li.append([_] + [int(x) for x in input().split()])

prev_P = 0
num_x_li = {}
for i in sorted(P_Y_li, key=lambda x:(x[1], x[2])):
    if prev_P != i[1]:
        # init
        prev_P = i[1]
        counter = 1
    num_x_li[i[0]] = counter
    counter += 1

for i in P_Y_li:
    print(str(i[1]).rjust(6,'0') + str(num_x_li[i[0]]).rjust(6,'0'))

Submission status: Accepted

Solution code:
from operator import itemgetter

N,M = map(int,input().split())
PY = []
for _ in range(M):
    P,Y = map(int,input().split())
    PY.append([_,P,Y])

s_PY = sorted(PY,key=itemgetter(1,2))

kenL = [0] * N
shiL = [''] * M

for i,p,y in s_PY:
    kenL[p-1] += 1
    shiL[i] = str(p).zfill(6) + str(kenL[p-1]).zfill(6)

for j in shiL:
    print(j)

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
P = []
for i in range(M):
    p, y = map(int,input().split())
    P.append([y, p ,i])
P.sort()

ken = [0] * N
shis = [''] * M

for y, p, i in P:
    ken[p-1] += 1
    shis[i] = str(p).zfill(6) + str(ken[p-1]).zfill(6)
    
for shi in shis:
    print(shi)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A = list(sorted([list(map(int, input().split())) + [i, 0] for i in range(M)]))
cur = 0
o = 1
for i, a in enumerate(A):
  if cur != a[0]:
    o = 1
    A[i][3] = o
    cur = a[0]
  else:
    o += 1
    A[i][3] = o

for a in sorted(A, key=lambda x: x[2]):
  print('{0:06d}{1:06d}'.format(a[0], a[3]))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
cities = [float("{}.{:010}".format(*tuple(map(int, input().split())))) for _ in range(M)]
sorted_cities = sorted(cities)

ids = {}
cnt = 1
before = -1
for c in sorted_cities:
    id_ = int(c)
    if before != id_:
        before = id_
        cnt = 1
    else:
        cnt += 1
    ids[c] = cnt

[print("{:06}{:06}".format(int(c), ids[c])) for c in cities]

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
cities = [int("{}{:010}".format(*tuple(map(int, input().split())))) for _ in range(M)]
sorted_cities = sorted(cities)

ids = {}
cnt = 1
before = -1
for c in sorted_cities:
    id_ = c//10000000000
    if before != id_:
        before = id_
        cnt = 1
    else:
        cnt += 1
    ids[c] = cnt

[print("{:06}{:06}".format(c//10000000000, ids[c])) for c in cities]

Submission status: Accepted

Solution code:
from sys import stdin
N, M = [int(_) for _ in stdin.readline().rstrip().split()]
PYs = [list(map(int, stdin.readline().rstrip().split()))+[i] for i in range(M)]
PYs.sort(key=lambda x:x[1])

num = [0]*N
ans = [""]*M

for p, y, i in PYs:
    num[p-1]+=1
    ans[i] = str(p).zfill(6) + str(num[p-1]).zfill(6)

for i in range(M):
    print(ans[i])

Submission status: Accepted

Solution code:
import sys
import re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits



def input(): return sys.stdin.readline().strip()


def INT(): return int(input())


def MAP(): return map(int, input().split())


def LIST(): return list(map(int, input().split()))

def update(bit,i, dp):
    bit[i] = dp
    return bit

def query(bit, i):
    lis = [bit[j] for j in range(i)]
    return max(lis)


sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

n,m=MAP()

py = [LIST() for _ in range(m)]
py = [[i,x[0],x[1]] for i,x in enumerate(py)]
lis=py.copy()
lis.sort(key=lambda x: (x[1], x[2]))

ans = [""] * m

tmp=1
ct = 1

for x in lis:
    if tmp!=x[1]:
        tmp = x[1]
        ct = 1
    ans[x[0]] = '{:06}{:06}'.format(x[1], ct)
    ct += 1
        
for x in ans:
    print(x)

Submission status: Accepted

Solution code:
import sys
import re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits



def input(): return sys.stdin.readline().strip()


def INT(): return int(input())


def MAP(): return map(int, input().split())


def LIST(): return list(map(int, input().split()))

def update(bit,i, dp):
    bit[i] = dp
    return bit

def query(bit, i):
    lis = [bit[j] for j in range(i)]
    return max(lis)


sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

n,m=MAP()

py = [LIST() for _ in range(m)]
py = [[i,x[0],x[1]] for i,x in enumerate(py)]
lis=deepcopy(py)
lis.sort(key=lambda x: (x[1], x[2]))

ans = [""] * m

tmp=1
ct = 1

for x in lis:
    if tmp!=x[1]:
        tmp = x[1]
        ct = 1
    ans[x[0]] = '{:06}{:06}'.format(x[1], ct)
    ct += 1
        
for x in ans:
    print(x)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
PY = [tuple(map(int, input().split())) for _ in range(M)]
PY_org = PY[:]

PY.sort(key=lambda py: py[1])

p_to_c_list = {}
for i in range(M):
    if p_to_c_list.get(PY[i][0]) == None:
        p_to_c_list[(PY[i][0])] = {'count': 1, 'city': {PY[i][1]: 1}}
    else:
        p_to_c_list[(PY[i][0])]['count'] += 1
        current_i = p_to_c_list[(PY[i][0])]['count']
        p_to_c_list[(PY[i][0])]['city'][PY[i][1]] = current_i

for py in PY_org:
    print('{:06}{:06}'.format(py[0], p_to_c_list[py[0]]['city'][py[1]]))

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, M = MAP()
PY = [LIST() for _ in range(M)]
PY_ = deepcopy(PY)
PY_.sort(key=lambda x: (x[0], x[1]))
# print(PY)
tmp = 0
i = 0
lis = []
dic = {}
for p, y in PY_:
	if p == tmp:
		i += 1
	else: # 県が変わったら
		lis.append([])
		tmp = p
		i = 1
	dic[str(p)+"_"+str(y)]=str(p).zfill(6)+str(i).zfill(6)

for p, y in PY:
	print(dic[str(p)+"_"+str(y)])