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 = list(map(int,input().split()))
tmp = [list(map(int,input().split())) for i in range(m)]
cities = [[] for i in range(n+1)]


for i,(pref,year) in enumerate(tmp):
    cities[pref].append([year,i])
    
answers = [""] * m
for i in range(n+1):
    for j,(year,index) in enumerate(sorted(cities[i])):
        answer = str(i).zfill(6) + str(j+1).zfill(6)
        answers[index] = answer
        
print(*answers,sep=("\n"))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
ken=[[] for i in range(n)]
for i in range(m):
    p,y=map(int,input().split())
    ken[p-1].append([i,y])
for i in range(n):
    ken[i].sort(key=lambda x:x[1])
ken0=[]
for i in range(n):
    for j in range(len(ken[i])):
        mae=str(i+1)
        ato=str(j+1)
        while len(mae)<6:
            mae='0'+mae
        while len(ato)<6:
            ato='0'+ato
        ken0.append([ken[i][j][0],mae+ato])
ken0.sort(key=lambda x:x[0])
for i in ken0:
    print(i[1])

Submission status: Accepted

Solution code:
n, m = [int(v) for v in input().split()]
cities = []
for i in range(m):
        py = tuple(int(v) for v in input().split())
        cities.append((py[1], py[0], i))
cities.sort()
nums = [None] * m
city_nums = {}
for city in cities:
        if not city[1] in city_nums:
                city_nums[city[1]] = 1
        else:
                city_nums[city[1]] += 1
        nums[city[2]] = str(city[1]).zfill(6) + str(city_nums[city[1]]).zfill(6)
for num in nums:
        print(num)

Submission status: Accepted

Solution code:
N,M = map(int, input().split())
pref = {}
city = [0] * M

for i in range(M):
    P,Y = map(int, input().split())
    if P not in pref.keys():
        pref[P] = []
    pref[P].append([i,Y])

for p in pref.keys():
    pref[p].sort(key=lambda e:e[1])
    for i,e in enumerate(pref[p]):
        city[e[0]] = '%06d%06d' % (p, i+1)

for c in city:
    print(c)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
city = []
for i in range(m):
    p, y = map(int, input().split())
    city.append([p,y,i])
city.sort(key = lambda x: x[1])
city.sort()
num = 1
for i in range(m):
    if i == 0:
        city[i][1] = num
        num += 1
    else:
        if city[i][0] == city[i-1][0]:
            city[i][1] = num
            num += 1
        else:
            city[i][1] = 1
            num = 2
city.sort(key = lambda x: x[2])
for i in range(m):
    p = format(city[i][0], '0>6')
    num = format(city[i][1], '0>6')
    print(p, end='')
    print(num)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
query_pairs = []
prefs = {}
for i in range(M):
    p, y = map(int, input().split())
    query_pairs.append([p, y])
    if p in prefs:
        prefs[p].append(y)
    else:
        prefs[p] = [y]

prefs_with_year_order = {}
for pref, years in prefs.items():
    years.sort()
    prefs_with_year_order[pref] = {}
    for i in range(len(years)):
        prefs_with_year_order[pref][years[i]] = i + 1 

for p, y in query_pairs:
    pref_part = "{0:06d}".format(p)
    order_part = "{0:06d}".format(prefs_with_year_order[p][y])
    print(pref_part + order_part)

Submission status: Accepted

Solution code:
from operator import itemgetter
pres = []
numbers = []
N,M = map(int, input().split())

for i in range(M):
    numbers.append('')

for i in range(N):
    pres.append([])

i = 0
for t in range(M):
    p,y = map(int,input().split())
    pres[p-1].append((y,i))
    i+=1

i = 0
for p in pres:
    i+=1
    if p==[]:
        continue
    front = '00000' + str(i)
    front = front[-6:]
    temp_p = p
    temp_p.sort(key=itemgetter(0))
    j = 0
    for city in temp_p:
        j+=1
        back = '00000' + str(j)
        back = back[-6:]
        numbers[city[1]] = front+back
        
for num in numbers:
    print(num)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
city = [[] for i in range(n)]
def f(s):
    s = str(s)
    t  = 6 - len(s)
    s = "0"*t + s
    return s
for i in range(m):
    ken,year = map(int,input().split())
    city[ken-1].append([year,i])
newcity = []
for i in range(n):
    city[i].sort()
    for j in range(len(city[i])):
        newcity.append([city[i][j][1],f(i+1) + f(j+1)])
newcity.sort()
for i in range(m):
    print(newcity[i][1])

Submission status: Accepted

Solution code:
N, M = [int(i) for i in input().split()]
data = list()
for i in range(M):
    p, y = [int(i) for i in input().split()]
    data.append([i, p, y])
data.sort(key=lambda x:(x[1],x[2]))
ind = 1
for j, (i, p, y) in enumerate(data):
    if (data[j-1][1] != p) and (j > 0):
        ind = 1
    data[j].append(ind)
    ind += 1
data.sort(key=lambda x:x[0])
for i, p, y, j in data:
    print(str(p).zfill(6) + str(j).zfill(6))

Submission status: Accepted

Solution code:
N, M = [int(i) for i in input().split()]
data = list()
for i in range(M):
    p, y = [int(i) for i in input().split()]
    data.append([i, p, y])
data.sort(key=lambda x:(x[1],x[2]))
ind = 1
for j, (i, p, y) in enumerate(data):
    if data[j-1][1] != p:
        ind = 1
    data[j].append(ind)
    ind += 1
data.sort(key=lambda x:x[0])
for i, p, y, j in data:
    print(str(p).zfill(6) + str(j).zfill(6))

Submission status: Accepted

Solution code:
n, m = [int(i) for i in input().split(" ")]
ps = []
pc = [0 for i in range(0, n + 1)]

for i in range(0, m):
    ps.append([i] + [int(i) for i in input().split(" ")] + [""])

ps = sorted(ps, key=lambda x: x[2])

for i in range(0, m):
    pc[ps[i][1]] += 1
    ps[i][3] = str(ps[i][1]).zfill(6) + str(pc[ps[i][1]]).zfill(6)

ps = sorted(ps, key=lambda x: x[0])

for i in range(0, m):
    print(ps[i][3])

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
no = 0
l = []
ans = []

cityNo = 0

beforeKen = 0

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

l.sort()

for j in l:
    if j[0] == beforeKen:
        cityNo += 1
    else:
        cityNo = 1

    ans.append([j[2], str(j[0]).zfill(6) + str(cityNo).zfill(6)])
    beforeKen = j[0]

ans.sort()

for k in ans:
    print(k[1])

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
L = []
for i in range(M):
  L.append(list(map(int,input().split())))
for j in range(M):
  L[j].append(j)
L.sort()
l = L[0][0]
cnt = 0
for k in range(M):
  if l == L[k][0]:
    cnt += 1
    L[k].append(cnt)
  else:
    l = L[k][0]
    cnt = 1
    L[k].append(cnt)
L = sorted(L, key = lambda x:x[2])
for i in range(M):
  print('0'*(6-len(str(L[i][0])))+str(L[i][0])+'0'*(6-len(str(L[i][3])))+str(L[i][3]))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import math
import sys
import heapq
from operator import itemgetter
input = sys.stdin.readline

# a = int(input().rstrip())
# a, b = map(int, input().rstrip().split())
# D = list(map(int, input().rstrip().split()))
# H = [int(input().rstrip()) for _ in range(L)]
# DD = [[0 for j in range(100)] for i in range(200)]
# dict = {} ## dictionary

# a = sorted(a, key=lambda x: x[1]))
# if __name__ == '__main__':

cities = dict()
N, M = map(int, input().rstrip().split())
for i in range(M):
	p, y = map(int, input().rstrip().split())
	if p not in cities:
		cities[p] = [[i, y]]
	else:
		cities[p].append([i, y])

heap_q = []	
for i in cities:
	tmp = sorted(cities[i], key=lambda x: x[1])
	for j in range(len(tmp)):
		heapq.heappush(heap_q, (tmp[j][0], i, j+1))

for i in range(M):
	x, y, z = heapq.heappop(heap_q)
	print(str(y).zfill(6) + str(z).zfill(6))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
t = []
for i in range(m):
    p,y = map(int, input().split())
    t.append([p, y, i])
target = sorted(t)
target[0].append(1)
cnt = 1
for i in range(1,m):
    if target[i][0]!=target[i-1][0]:
        cnt = 1
    else:
        cnt += 1
    target[i].append(cnt)
ans = sorted(target, key=lambda x:x[2])
for i in range(m):
    print(str(ans[i][0]).zfill(6) + str(ans[i][3]).zfill(6))

Submission status: Accepted

Solution code:
def main():
    N, M = list(map(int, input().split()))
    cityList = {}
    for i in range(M):
        P, Y = list(map(int, input().split()))
        if not P in cityList:
            cityList[P] = [[i, Y]]
        else:
            cityList[P].append([i, Y])
    for value in cityList.values():
        value.sort(key=lambda city: city[1])
    cityNumList = []
    for key, value in cityList.items():
        for i in range(len(value)):
            cityNumList.append([value[i][0], "{:06d}{:06d}".format(key, i+1)])
    cityNumList.sort(key=lambda city: city[0])
    for cityNum in cityNumList:
        print(cityNum[1])

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

count=[0]*N
ans=[]

for i in data:
    count[i[0][0]-1] += 1
    ans.append([i[1],str(i[0][0]).zfill(6) + str(count[i[0][0]-1]).zfill(6)])

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

for i in ans:
    print(i[1])

Submission status: Accepted

Solution code:
def read():
    return int(input())

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

n,m = reads()
cnt = {k:[] for k in range(n+1)}
buf = [None]*m
for i in range(m):
    p,y = reads()
    cnt[p].append((y,i))
for p,l in cnt.items():
    if not l:
        continue
    l.sort()
    for j,(y,i) in enumerate(l):
        buf[i] = '{:06d}{:06d}'.format(p,j+1)

print('\n'.join(buf))

Submission status: Accepted

Solution code:
import numpy as np

N,M = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(M)]
order = [[] for _ in range(N)]
for p,y in X:
    order[p-1].append(y)
#X = np.array(X, dtype=int)
for i in range(N):
    order[i] = np.argsort(np.argsort(order[i]))
cnts = [0 for _ in range(N)]
for i in range(M):
    p = X[i][0]
    print('{:06}{:06}'.format(p, order[p-1][cnts[p-1]]+1) )
    cnts[p-1] += 1

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc113/tasks/abc113_c

N, M = map(int, input().split())
c_l = [[int(i) for i in input().split()] + [j] for j in range(M)]

# print(c_l)
c_l.sort(key=lambda x: x[1])

counter = [0] * (N+1)
for c in c_l:
    p = c[0]
    counter[p] += 1
    c.append("{:06}{:06}".format(c[0], counter[p]))

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

for c in c_l:
    print(c[3])

Submission status: Accepted

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

ken = [(i,) + tuple(map(int,input().split())) for i in range(m)]

def func(elem):
    return elem[1:3]
ken.sort(key=func)

currKen = ken[0][1]
cnt = 1
for i in range(len(ken)):
    if ken[i][1] == currKen:
        ken[i] +=(cnt,)
        cnt += 1
    else:
        currKen = ken[i][1]
        cnt = 1
        ken[i] +=(cnt,)
        cnt += 1


#print(ken)
ken = sorted(ken,key = lambda x: x[0])

for k in ken:
    print("%.6d%.6d"%(k[1],k[3]))

Submission status: Accepted

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

Num = [0]*(N+1)

for i in range(M):
    p = X[i][0]
    Num[p] += 1
    c = Num[p]
    X[i].append(str(p).zfill(6) + str(c).zfill(6))

X.sort(key=lambda x: x[2])
for i in range(M):
    print(X[i][3])

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
L = []
for i in range(M):
    l = list(map(int,input().split()))+[i]
    L.append(l)
cnt = 0
tmp = []
M = sorted(L,key = lambda x: (x[0],x[1]))
for x in M:
    if tmp == x[0]:
        x.append(cnt+1)
        cnt += 1
    else:
        tmp = x[0]
        cnt = 0
        x.append(cnt)
M = sorted(L,key = lambda x:x[2])
#print(M)
for x in M:
    st = str(x[0]).zfill(6)
    st += str(x[3]+1).zfill(6)
    print(st)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

city = []

for i in range(M):
    P, Y = map(int, input().split())
    city.append([i, P, Y])
city.sort(key=lambda x: x[2])

count = defaultdict(lambda: 0)
for c in city:
    count[c[1]] += 1
    c.append(count[c[1]])
city.sort(key=lambda x: x[0])

for _, P, _, n in city:
    print(format(P, '06') + format(n, '06'))

Submission status: Accepted

Solution code:
def main() -> None:
    N, M = map(int, input().split())
    PYT = [tuple(map(int, input().split())) for _ in range(M)]
    PYTS = sorted(PYT)

    before = 0
    tmp = {}
    for py in PYTS:
        if before != py[0]:
            # 初期化する
            before = py[0]
            count = 0
        count += 1
        tmp[py] = count

    for py in PYT:
        print("{:06}{:06}".format(py[0], tmp[py]))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
L = [list(map(int, input().split())) for _ in range(M)]
Y = sorted([(i, (p, y)) for i, (p, y) in enumerate(L)], key=lambda x: x[1])
result = [""] * M
x = 0
before_p = 0
for i, (p, y) in Y:
    if before_p != p:
        x = 0
        before_p = p
    x += 1
    result[i] = "{:06}{:06}".format(p, x)
for r in result:
    print(r)

Submission status: Accepted

Solution code:
r=lambda i:('0'*6+str(i))[-6:]
I=lambda:map(int,input().split())
N,M=I()
C=[[i]+list(I())for i in range(M)]
C=sorted(C,key=lambda x:(x[1],x[2]))
q=1;c=1;l=[]
for i,p,_ in C:q,c=(p,1)if p>q else (q,c);l+=[[i,r(p)+r(c)]];c+=1
for _,s in sorted(l,key=lambda x:(x[0])):print(s)

Submission status: Accepted

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

PY_sort = sorted(PY)

tmp = dict()

before = 0
for py in PY_sort:
    if before != py[0]:
        before = py[0]
        count = 0
    count += 1
    tmp[py] = count

for py in PY:
    print("{:06}{:06}".format(py[0],tmp[py]))

Submission status: Accepted

Solution code:
from bisect import bisect_left
n,m=map(int,input().split())
ls=[[] for i in range(n)]
py=[]
for i in range(m):
  p,y=map(int,input().split())
  ls[p-1].append(y)
  py.append([p,y])
ls=list(map(lambda x:sorted(x),ls))
for i in range(m):
  p,y=py[i]
  index= bisect_left(ls[p-1],y)
  print(str(p).zfill(6)+str(index+1).zfill(6))

Submission status: Accepted

Solution code:
def inpl(): return list(map(int, input().split()))
N, M = inpl()
A = [""]*M
P = [[] for _ in range(N+1)]
for i in range(M):
    p, y = inpl()
    P[p].append((y, i))

for p, prefecture in enumerate(P):
    prefecture = sorted(prefecture, key=lambda x: x[0])
    for j, (y, i) in enumerate(prefecture):
        A[i] = "{}{}".format(str(p).zfill(6), str(j+1).zfill(6))

print(*A, sep="\n")

Submission status: Accepted

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

cities = {}
prefs = []

for i in range(1, M + 1):
  p, y = list(map(int, input().split()))
  
  pref = {"city": p, "year": y}
  prefs.append(pref)

  if p not in cities:
    cities[p] = [pref]
  else:
    cities[p].append(pref)

for city in cities.values():
  city.sort(key=lambda p: p['year'])
  for idx, pref in enumerate(city):
    pref['pref_id'] = str(idx + 1).zfill(6)

[print("%s%s" % (
  str(int(pref['city'])).zfill(6), 
  pref['pref_id'])) for pref in prefs]

Submission status: Accepted

Solution code:
n,m=list(map(int,input().split(" ")))
py=[]
for i in range(m):
    py.append(list(map(int,input().split(" ")))+[i])
py.sort()
ids = []
c=1
p=1
for j in py:
    if j[0] != p:
        c=1
        p=j[0]
    ids.append([j[2],"{:0>6}{:0>6}".format(j[0],c)])
    c+=1
ids.sort()
for i in ids:
    print(i[1])

Submission status: Accepted

Solution code:
n, m = list(map(int, input().split()))
li = []
yli = []
for _ in range(m):
    p, y = list(map(int, input().split()))
    li.append((y, p))
    yli.append(y)

import numpy as np
idx = np.argsort(yli).argsort()
srt = sorted(li)
ans = []
from collections import Counter
pcnt = Counter()
for y, p in srt:
    pcnt[p] += 1
    ans.append('{:06}{:06}'.format(p, pcnt[p]))

for i in idx:
    print(ans[i])

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
PY = [list(map(int,input().split()))+[0] for _ in range(M)]
sort_PY = sorted(PY, key = lambda x: x[1])
city = {}
for py in sort_PY:
  if(py[0] in city):
    city[py[0]] += 1
  else:
    city[py[0]] = 1
  py[2] = city[py[0]]
for py in PY:
  print(str(py[0]).zfill(6) + str(py[2]).zfill(6))

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
l = []
for i in range(m):
    l.append([i]+list(map(int, input().split())))
l = sorted(l, key=lambda x:(x[1],x[2]))
ind = 0
id = []
for i in range(n):
    nature = i+1
    j = 1
    while ind<len(l) and l[ind][1]==nature:
        id.append([l[ind][0],nature,j])
        j+=1
        ind+=1
id = sorted(id, key=lambda x:x[0])
for i in range(len(id)):
    print('{:0=6}'.format(id[i][1])+'{:0=6}'.format(id[i][2]))

Submission status: Accepted

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

L = sorted(L, key = lambda x:x[2])

for l in L:
    P[l[1]] += 1
    l[3] = P[l[1]]    
        
for l in sorted(L, key = lambda x:x[0]):
    print('{0:0>6d}{1:0>6d}'.format(l[1], l[3]))

Submission status: Accepted

Solution code:
a,b=map(int,input().split())
L=[[] for i in range(a)]
u=0
# i番目の県の情報（[i，年，入力順]）をLのi番目に入れる
for i in range(b):
    u+=1
    c=list(map(int,input().split()))
    c.append(u)
    L[int(c[0])-1].append(c)
# Lの要素を年でソート
for i in L:
    i.sort(key=lambda x:x[1])
#　ソートしたので、要素ごとに何番目にできたかを末尾に付け加えておく
for i in L:
    e=0
    for j in i:
        e+=1
        j.append(e)
q=[]
for w in L:
   q.extend(w)# flatten
# 入力順に並べ替えて、入力した順に出力できるようにする
q.sort(key=lambda x:x[2])
for r in range(b):
        print(str(q[r][0]).zfill(6)+str(q[r][3]).zfill(6))# zfill

Submission status: Accepted

Solution code:
a,b=map(int,input().split())
L=[[] for i in range(a)]
u=0
for i in range(b):
    u+=1
    c=list(map(int,input().split()))
    c.append(u)
    L[int(c[0])-1].append(c)
for i in L:
    i.sort(key=lambda x:x[1])
for i in L:
    e=0
    for j in i:
        e+=1
        j.append(e)
q=[]
for w in L:
   q.extend(w) 
q.sort(key=lambda x:x[2])
for r in range(b):
        print(str(q[r][0]).zfill(6)+str(q[r][3]).zfill(6))

Submission status: Accepted

Solution code:
a,b=map(int,input().split())
L=[[] for i in range(a)]
u=0
for i in range(b):
    u+=1
    c=list(map(int,input().split()))
    c.append(u)
    L[int(c[0])-1].append(c)
for i in L:
    i.sort(key=lambda x:x[1])
for i in L:
    e=0
    for j in i:
        e+=1
        j.append(e)
q=[]
for w in L:
   q.extend(w) 
q.sort(key=lambda x:x[2])
for r in range(b):
        print('0'*(6-len(str(q[r][0])))+str(q[r][0])+'0'*(6-len(str(q[r][3])))+str(q[r][3]))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
ken = [[] for i in range(N)]
Y = []
for i in range(M):
    p, y = map(int, input().split())
    Y.append(y)
    ken[p-1].append(i)
# print(ken)
for i in range(len(ken)):
    ken[i].sort(key=lambda x: Y[x])
# print(ken)

ans = ["0"] * M
for i in range(len(ken)):  # i:ken番号
    for j in range(len(ken[i])):  # j:県の中でj番目
        ans[ken[i][j]] = str(i+1).zfill(6) + str(j+1).zfill(6)
for a in ans:
    print(a)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
arr = []
for i in range(M):
  pi,yi = map(int,input().split())
  arr.append((pi,yi))
sorted_arr = sorted(arr, key=lambda x:x[1])
numof_i_in_p = [1]*N
id_map = dict()
for factor in sorted_arr:
  id = "{:0>6}{:0>6}".format(factor[0], numof_i_in_p[factor[0]-1])
  numof_i_in_p[factor[0]-1] += 1
  id_map[factor]=id
for factor in arr:
  print(id_map[factor])

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

class City(object):
    def __init__(self, i, year):
        self.i = i
        self.year = year
        self.id = None

    def __lt__(self, other):
        return self.year < other.year

    def __eq__(self, other):
        return self.year == other.year

    def __gt__(self, other):
        return self.year > other.year


class Solver(object):
    def __init__(self):
        self.n, self.m = list(map(int, input().split(" ")))
        self.prefectures = [[] for _ in range(self.n)]
        self.cities = []
        for i in range(self.m):
            p, y = list(map(int, input().split(" ")))
            city = City(i+1, y)
            self.cities.append(city)
            heappush(self.prefectures[p-1], city)

    def solve(self):
        for i in range(self.n):  # For each prefecture Pi
            for j in range(len(self.prefectures[i])):  # For each Cj in Pi
                city = heappop(self.prefectures[i])
                city.id = "{:06d}{:06d}".format(i+1, j+1)
        for city in self.cities:
            print(city.id)


if __name__ == "__main__":
    s = Solver()
    s.solve()

Submission status: Accepted

Solution code:
import sys

def main():
  input = sys.stdin.readline
  N, M = map(int, input().split())
  C = [0] * M  # Num of City, P, Y, Num of birth in Y
  P = [0] * (N+1)
  for m in range(M):
    p, y = map(int, input().split())
    C[m] = [m, p, y, 0]
  C = sorted(C, key=lambda x: x[2])

  for c in C:
    P[c[1]] += 1
    c[3] = P[c[1]]
  C = sorted(C, key=lambda x: x[0])

  for c in C:
    print('{:06d}{:06d}'.format(c[1], c[3]))


if __name__ == '__main__':
  main()

Submission status: Accepted

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

num = 1
pref = 0
for city in cities:
    if pref != city[1]:
        pref = city[1]
        num = 1
    city = city.append(num)
    num += 1

cities = sorted(cities, key=lambda x: x[0])

for city in cities:
    print(str(city[1]).zfill(6) + str(city[3]).zfill(6))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

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

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

ID = [0] * M
tp, id = 1, 0
for i in range(M):
    p, y, ix = D[i]
    if tp == p:
        id += 1
    else:
        tp, id = p, 1
    ID[ix] = (p, id)

for i in range(M):
    print("{:0>6}{:0>6}".format(ID[i][0], ID[i][1]))

Submission status: Accepted

Solution code:
import heapq


def pad(p):
    n = 1
    q = p
    while True:
        q = q // 10
        if q == 0:
            break
        n += 1
    return "0" * (6 - n) + str(p)


n, m = list(map(int, input().split(' ')))
ps = []
ys = []
year_ids = {}
heaps = {}
for i in range(m):
    p, y = list(map(int, input().split(' ')))
    ps.append(p)
    ys.append(y)
    if p not in heaps:
        heaps[p] = []
        year_ids[p] = {}
    heapq.heappush(heaps[p], y)



for p in heaps:
    yid = 1
    while True:
        if len(heaps[p]) == 0:
            break
        y = heapq.heappop(heaps[p])
        year_ids[p][y] = yid
        yid += 1


for i in range(m):
    p = ps[i]
    y = ys[i]
    x = year_ids[p][y]
    print(pad(p) + pad(x))

Submission status: Accepted

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

X=[]

for i in range(m):
    a=i
    b,c=map(int,input().split())
    X.append([a,b,c])

sort_X=sorted(X,key=lambda x:(x[1],x[2]))
sort_X[0].append(1)

for i in range(1,m):
    if sort_X[i][1]!=sort_X[i-1][1]:
        sort_X[i].append(1)
    else:
        sort_X[i].append(sort_X[i-1][3]+1)
   
X=sorted(sort_X,key=lambda x:x[0])
for i in range(m):
    count=X[i][3]
    first_num="000000"
    last_num="000000"
    
    
    first_num=first_num[:6-len(str(X[i][1]))]+str(X[i][1])
    last_num=last_num[:6-len(str(count))]+str(count)
    print(first_num+last_num)

Submission status: Accepted

Solution code:
N,M = map(int, input().split())
py = [(0,0,0)]*M
for i in range(M):
    p,y = map(int,input().split())
    py[i] = (p,y,i)

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

ans = [(0,0)]*M

year = 1
tmp_city = 0

for index, i in enumerate(py):
    city_str = "{}".format(i[0]).zfill(6)
    if tmp_city != i[0]:
        year = 1
    year_str = "{}".format(year).zfill(6)
    tmp_city = i[0]
    year += 1
    
    ans_str = city_str + year_str
    
    ans[index] = (ans_str,i[2])

ans.sort(key=lambda x:x[1])
for i in ans:
    print(i[0])

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
PY = []
for i in range(M):
    PY.append(list(map(int, input().split())))
P_dict = {}
res_dict = {}
for i in range(1, N+1):
    P_dict[i] = []
    res_dict[i] = []
for n, i in enumerate(PY):
    P_dict[i[0]].append((i[1], n))
res = []
for i in range(1, N+1):
    P_dict[i] = sorted(P_dict[i], key=lambda x:x[0])
    tmp_P_num = '{}'.format(i).zfill(6)
    res += [(tmp_P_num + '{}'.format(nn+1).zfill(6), n[1]) for nn, n in enumerate(P_dict[i])]
res = sorted(res, key=lambda x:x[1])
for i in res:
    print(i[0])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding:utf-8 -*-

def main():
  n, m = map(int, input().split())
  ipy = [(i+1, )+(tuple(map(int, input().split()))) for i in range(m)]
  ipy.sort(key=lambda x:x[2])
  kens = set([p for i,p,y in ipy])
  di = {ken:0 for ken in kens}

  ans = []
  for i,p,y in ipy:
    di[p] += 1
    number = ('%06d%06d' % (p, di[p]))
    ans += [(i, number)]
  ans.sort(key=lambda x:x[0])

  for _, number in ans:
    print(number)
  pass

if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
dic = {}
raw = []
dic[1] = []
for i in range(M):
  P, Y = map(int, input().split())
  raw.append([P, Y, i])
raw.sort()
for i in range(M):
  if i == 0:
    raw[i][1] = 1
    p, y, ind = raw[i]
    continue
  pp, yy, iind = raw[i]
  if pp == p:
    raw[i][1] = y + 1
  else:
    raw[i][1] = 1
  p, y, ind = raw[i]
raw.sort(key = lambda x:x[2])
for r in raw:
    p, y, ind = r
    P = "{0:06d}".format(p)
    Y = "{0:06d}".format(y)
    print(P+Y)

Submission status: Accepted

Solution code:
import numpy as np
import math
from collections import defaultdict

n,m = input().split()
n = int(n)
m = int(m)
P,Y = [],[]
for _ in range(m):
	p,y = input().split()
	P.append(p)
	Y.append(y)

P = [int(p) for p in P]
Y = [int(y) for y in Y]

sorted = defaultdict(list)

sorted = [[] for i in range(n)]

for i,(p,y) in enumerate(zip(P,Y)):
	sorted[p-1].append((y,i))

ans = [None]*m
for i, d in enumerate(sorted):
	d.sort()
	for k, (y, j) in enumerate(d):
		ans[j] = "%06d%06d" % (i+1,k+1)
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
D = [[] for i in range(N)]
for i in range(M):
    p, y = map(int, input().split())
    D[p-1].append((y, i))
ans = [None]*M
for i, d in enumerate(D):
    d.sort()
    for k, (y, j) in enumerate(d):
        ans[j] = "%06d%06d" % (i+1,k+1)
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
# https://qiita.com/_-_-_-_-_/items/34f933adc7be875e61d0
# abcde	s=input()	s='abcde'
# abcde	s=list(input())	s=['a', 'b', 'c', 'd', 'e']
# 5(1つだけ)	a=int(input())	a=5
# 1 2	x,y = map(int,input().split())	x=1,y=2
# 1 2 3 4 5 ... n 　	li = input().split()	li=['1','2','3',...,'n']
# 1 2 3 4 5 ... n 　	li = list(map(int,input().split()))	li=[1,2,3,4,5,...,n]
# FFFTFTTFF 　	li = input().split('T')	li=['FFF', 'F', '', 'FF']

# 3
# hoge
# foo
# bar
# n=int(input())
# string_list=[input() for i in range(n)]
# N, M = map(int,input().split())

# P, Y = [], []
# for _ in range(M):
#     P_i, Y_i = map(int,input().split())
#     P.append(P_i)
#     Y.append(Y_i)
def inpl(): return list(map(int, input().split()))

N, M = inpl()
A = [""]*M
P = [[] for _ in range(N+1)]
for i in range(M):
  p, y = inpl()
  P[p].append((y, i))

# print(P)
for ind, p in enumerate(P):
  p = sorted(p, key=lambda x: x[0])
  for j, (y, i) in enumerate(p):
    A[i] = "{}{}".format(str(ind).zfill(6), str(j+1).zfill(6))

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

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
city=[]
for i in range(m):
    a=i
    b,c=map(int,input().split())
    city.append([a,b,c])
city=sorted(city,key=lambda x:(x[1],x[2]))
judge=1
count=1
for i in range(m):
    if city[i][1]==judge:
        city[i].append(count)
        count+=1
    else:
        city[i].append(1)
        judge=city[i][1]
        count=2
for i in range(m):
    city[i].append(str(city[i][1]).zfill(6)+str(city[i][3]).zfill(6))
city=sorted(city,key=lambda x:x[0])
for i in range(m):
    print(city[i][4])

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
city=[]
for i in range(m):
    a=i
    b,c=map(int,input().split())
    city.append([a,b,c])
city=sorted(city,key=lambda x:(x[1],x[2]))
city[0].append(1)
for i in range(1,m):
    if city[i][1]!=city[i-1][1]:
        city[i].append(1)
    else:
        city[i].append(city[i-1][3]+1)
for i in range(m):
    city[i].append(str(city[i][1]).zfill(6)+str(city[i][3]).zfill(6))
city=sorted(city,key=lambda x:(x[0]))
for i in range(m):
    print(city[i][4])

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
PY = [list(map(int,input().split())) + [0] for _ in range(M)]
sort_PY = sorted(PY, key = lambda x: x[1])
num = {}
for py in sort_PY:
  if(py[0] not in num):
    num[py[0]] = 1
  else:
    num[py[0]] += 1
  py[2] = num[py[0]]
for py in PY:
  print(str(py[0]).zfill(6) + str(py[2]).zfill(6))

Submission status: Accepted

Solution code:
n,m=map(int, input().split())
l = [[int(i) for i in input().split()] for i in range(m)]

for i in range(m):
    l[i].append(i)
l = sorted(l,key=lambda x: (x[0],x[1]))

l[0].append(1)
for i in range(1,m):
    if l[i][0]!=l[i-1][0]:
        l[i].append(1)
    else:
        l[i].append(l[i-1][3]+1)

for i in range(m):
    l[i].append(str(l[i][0]).zfill(6) + str(l[i][3]).zfill(6))

l=sorted(l,key=lambda x:(x[2]))

for i in range(m):
    print(l[i][4])