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())
l = []
for i in range(M):
    P, Y = map(int, input().split())
    l.append([i, P, Y])
l = sorted(l, key = lambda x: (x[1], x[2]))
ans = []
prev_P = 0
for i in range(M):
    if prev_P != l[i][1]:
        j = 0
    j += 1
    ans.append([l[i][0], str(l[i][1]).zfill(6) + str(j).zfill(6)])
    prev_P = l[i][1]
ans = sorted(ans)
for i, s in ans:
    print(s)

Submission status: Accepted

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

py = [list(map(int,input().split())) for _ in range(m)]

for ppyy in py:
  city_list[ppyy[0]-1].append(ppyy[1])

dict = {}
for index, ppyy in enumerate(city_list):
  ppyy.sort()
  for index2, pppyyy in enumerate(ppyy):
    dict[pppyyy] = (str(index+1).zfill(6)+str(index2+1).zfill(6))

for ppyy in py:
  print(dict[ppyy[1]])

Submission status: Accepted

Solution code:
from sys import stdin
input = stdin.readline
n, m = map(int, input().split())

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

built = [1]*n
for i in range(m):
    ans[i][1] = built[ans[i][0]-1]
    built[ans[i][0]-1] += 1

for i in sorted(ans,key=lambda x:x[2]): print("%06d%06d" % (i[0],i[1]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n, m = list(map(int, input().split()))
data = []
for i in range(m):
    data.append([i + 1] + list(map(int, input().split())))
    #data[0::] = cityNumber,
    #data[:0:] = prefect,
    #data[::0] = year
data = sorted(data, key = lambda x: (x[1], x[2]))
#prefect => year
ans = [[0,0,0] for i in range(m)]
#ans[::0] = city Number
#ans[0::] = prefect
#ans[:0:] = ID

pre = data[0][1]
num = 0
for i in range(m):
    ans[i][0] = data[i][1] # prefect
    ans[i][2] = data[i][0] #cityNumber
    if pre == data[i][1]:
        num += 1
    else:
        num = 1
    ans[i][1] = num
    pre = data[i][1]
ans = sorted(ans, key = lambda x:x[2])
for i in range(m):
    print("{:0=6}{:0=6}".format(ans[i][0],ans[i][1]))

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
py = []
for i in range(m):
  a,b = map(int, input().split())
  py.append([a,b,i])
py.sort()
p = py[0][0]
y = 1
for i in range(m):
  if py[i][0] == p:
    py[i][1] = y
    y += 1
  else:
    py[i][1] = 1
    y = 2
    p = py[i][0]
py = sorted(py, key=lambda x:x[2])
for p,y,i in py:
  print("{:0=6}{:0=6}".format(p,y))

Submission status: Accepted

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

for i in py:
  ken[i[1]-1].append(i)
ans=[[i[1]] for i in py]
for i in ken:
  i.sort(key=lambda x:x[2])
  for j in range(len(i)):
    ans[i[j][0]].append(j+1)

for p,x in ans:
  print("".join([str(p).zfill(6),str(x).zfill(6)]))

Submission status: Accepted

Solution code:
from operator import itemgetter

N, M = map(int, input().split())
P = []
Y = []
IDX = []

for idx in range(M):
    p, y = map(int, input().split())
    P.append(p)
    Y.append(y)
    IDX.append(idx)
    
PYIDX = zip(P,Y,IDX)
PYIDX = sorted(PYIDX, key=itemgetter(1))
PYIDX = sorted(PYIDX, key=itemgetter(0))
PYIDX = [list(x) for x in PYIDX]

for i in range(M):
    if i == 0 or PYIDX[i-1][0] != PYIDX[i][0]:
        city_number = 1
    else:
        city_number += 1
    PYIDX[i].append(str(PYIDX[i][0]).zfill(6) + str(city_number).zfill(6))

PYIDX = sorted(PYIDX, key=itemgetter(2))

for idx in range(M):
    print(PYIDX[idx][3])

Submission status: Accepted

Solution code:
# 二分探索
from bisect import bisect_left

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

t = [[] for _ in range(N)]
for P, Y in PY:
    t[P - 1].append(Y)

for i in range(N):
    t[i].sort()

for P, Y in PY:
    print("%06d%06d" % (P, bisect_left(t[P - 1], Y) + 1))

Submission status: Accepted

Solution code:
def slove():
    import sys
    input = sys.stdin.readline
    n, m = list(map(int, input().rstrip('\n').split()))
    py = []
    ls = [1] * (n + 1)
    for i in range(m):
        p, y = list(map(int, input().rstrip('\n').split()))
        py.append([p, y, 0, i])
    py.sort()
    for i in range(m):
        py[i][2] = ls[py[i][0]]
        ls[py[i][0]] += 1
    py.sort(key=lambda x: x[3])
    for i in range(len(py)):
        a = ["0"] * 6
        a = a + list(str(py[i][0]))
        a = a[-6:]
        b = ["0"] * 6
        b = b + list(str(py[i][2]))
        b = b[-6:]
        print("".join(a + b))


if __name__ == '__main__':
    slove()

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
city = list(enumerate([list(map(int,input().split())) for _ in range(m)]))
city.sort(key = lambda x:(x[1][0],x[1][1]))
city_dict = {}
for c in city:
  if c[1][0] in city_dict:
    city_dict[c[1][0]] += 1
    c[1][1] = city_dict[c[1][0]]
  else:
    city_dict[c[1][0]] =1
    c[1][1] = city_dict[c[1][0]]

city.sort(key = lambda x:x[0])
for c in city:
  num = str(c[1][0]*10**6+c[1][1])
  print("0"*(12-len(num))+num)

Submission status: Accepted

Solution code:
from collections import defaultdict
import bisect
n,m=map(int,input().split())
py=[[int(i) for i in input().split()] for _ in range(m)]

dic=defaultdict(list)
for  p,y in sorted(py):
    dic[p]+=[y]
for p,y in py:
    idx=bisect.bisect_right(dic[p],y)
    print('{:06g}{:06g}'.format(p,idx))

Submission status: Accepted

Solution code:
(n, m) = map(int, input().split())
cities = {}
for i in range(m):
    (pref, year) = map(int, input().split())
    if not pref in cities.keys():
        cities[pref] = []
    cities[pref].append((i, year))


def get_id(pref, index):
    return "{}{}".format(str(pref).zfill(6), str(index).zfill(6))


ids = []
for key, values in cities.items():
    values.sort(key=lambda x: x[1])
    for i, value in enumerate(values):
        ids.append((value[0], get_id(key, i + 1)))
ids.sort(key=lambda x: x[0])
for id in ids:
    print(id[1])

Submission status: Accepted

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


length = [list(map(int,input().split())) for _ in range(M)]
for i in range(M):
  length[i].insert(2,i)
length = sorted(length)
ans_list =[0]*M
count = 1
for i in range(M):
  if i == 0:
    ans = str(length[i][0]).zfill(6) + str(count).zfill(6)
    ans_list[i] = [length[i][2],ans]
  elif i >= 1 and length[i][0] == length[i-1][0]:
    count += 1
    ans = str(length[i][0]).zfill(6) + str(count).zfill(6)
    ans_list[i] = [length[i][2],ans]
  elif i >= 1 and length[i][0] != length[i-1][0]:
    count = 1
    ans = str(length[i][0]).zfill(6) + str(count).zfill(6)
    ans_list[i] = [length[i][2],ans]
ans_list.sort(key=lambda x: x[0])
for i in range(M):
  print(ans_list[i][1])

Submission status: Accepted

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

cnt = [1]*(N+1)
for j in sorted(PY, key=lambda x: x[1]):
  j.append("{:06d}{:06d}".format(j[0], cnt[j[0]]))
  cnt[j[0]] += 1

for k in PY:
  print(k[2])

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
data=[list(map(int,input().split()+[i])) for i in range(M)]
data=sorted(data,key=lambda x:x[1])
data=sorted(data,key=lambda x:x[0])
preP=None
count=None
printdata=[]
for i in data:
    if preP==i[0]:
        count+=1
    else:
        preP=i[0]
        count=1
    printdata.append(["0"*(6-len(str(preP)))+str(preP)+"0"*(6-len(str(count)))+str(count),i[2]])
printdata=sorted(printdata,key=lambda x:x[1])
for i in printdata:
    print(i[0])

Submission status: Accepted

Solution code:
import numpy as np


def solve(N, M, py):
    ans = np.zeros(M, dtype=object)
    rank = [1]*(N+1)

    py.sort()

    for pyi in py:
        pi = pyi[1]
        ans[pyi[2]] = str(pi).zfill(6) + str(rank[pi]).zfill(6)
        rank[pi] += 1

    return ans


if __name__ == "__main__":
    _p, _y = 0, 0
    py = []

    N, M = map(int, input().split())
    for i in range(M):
        _p, _y = map(int, input().split())
        py.append((_y, _p, i))

    ans = solve(N, M, py)
    for a in ans:
        print(a)

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
py = []
for i in range(m):
    city = list(map(int, input().split()))
    city.append(i)
    py.append(city)
py.sort()
for i in range(m):
    if py[i][0]==py[i-1][0] and i!=0:
        py[i][1]=py[i-1][1]+1
    else:
        py[i][1]=1 

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

for i in range(m):
    
    py[i][0] = str(py[i][0])
    py[i][1]=str(py[i][1])
    while len(py[i][1])<6:
        py[i][1]="0"+py[i][1]
        
    while len(py[i][0])<6:
        py[i][0]="0"+py[i][0]
    print(py[i][0]+py[i][1])

Submission status: Accepted

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

Pstr=[]
for i in range(N+1):
    SL=len(str(i))
    Pstr.append("0"*(6-SL)+str(i))
PY=[]
for i in range(1,M+1):
    P,Y=map(int,input().split())
    PY.append([i,P,Y])

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

cnt=0
ans=[]
for i in range(M):
    if cnt==0:
        Ps=Pstr[PY[i][1]]
        Ylis=[]
        Ylis.append([PY[i][0],PY[i][2]])
        cnt=1
    elif PY[i-1][1]==PY[i][1]:
        Ylis.append([PY[i][0],PY[i][2]])
    else:
        Ylis.sort(key=lambda x:x[1])
        for j in range(len(Ylis)):
            YL=len(str(j+1))
            temp=Ps+("0"*(6-YL))+str(j+1)
            ans.append([Ylis[j][0],temp])
        Ps=Pstr[PY[i][1]]
        Ylis=[]
        Ylis.append([PY[i][0],PY[i][2]])
        cnt=1
Ylis.sort(key=lambda x:x[1])
for j in range(len(Ylis)):
    YL = len(str(j + 1))
    temp = Ps + ("0" * (6 - YL)) + str(j + 1)
    ans.append([Ylis[j][0], temp])

ans.sort()

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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
lst = [[] for _ in range(n + 1)]
py = [tuple(map(int, input().split())) for i in range(m)]

for i, (p, y) in enumerate(py):
    lst[p].append((y, i))

ans = [None] * m

for p, l in enumerate(lst):
    l.sort()
    for j, (y, i) in enumerate(l):
        ans[i] = str(p).zfill(6) + str(j + 1).zfill(6)

print(*ans, sep=('\n'))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
A=[[i,list(map(int,input().split()))] for i in range(m)]
A.sort(key=lambda x:x[1][1])
B={}
for x,y in A:
    if y[0] not in B:
        B[y[0]]=1
        y[1]=1
    else:
        B[y[0]] +=1
        y[1]=B[y[0]]

for i in sorted(A,key=lambda x:x[0]):
    print(str(i[1][0]).zfill(6)+str(i[1][1]).zfill(6))

Submission status: Accepted

Solution code:
from bisect import bisect_left
from collections import deque
N,M = map(int,input().split())
PY = []
S =[[] for _ in range(N)]

for i in range(M):
    PY.append(list(map(int,input().split())))
    S[PY[i][0]-1].append(PY[i][1])

for i in range(N):
	S[i].sort()

for i in range(M):
    x = bisect_left(S[PY[i][0]-1],PY[i][1])+1
    print(str(PY[i][0]).zfill(6)+str(x).zfill(6))

Submission status: Accepted

Solution code:
import bisect

n, m = map(int, input().split())
data = [list(map(int, input().split())) for _ in range(m)]  # 市iの順番を保つ
py_list = [[] for _ in range(n)]  # 市iの(属する県, 誕生年)

for p, y in data:
    py_list[p-1].append(y)

for i in range(n):
    py_list[i].sort()

for p, y in data:
    pos = bisect.bisect_left(py_list[p-1], y) + 1
    print("%06d%06d" % (p, pos))

Submission status: Accepted

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

for i in range(m):
    p,y = map(int,input().split())
    prefs[p-1].append((y,i))
for pref in prefs:
    pref.sort()

answers = []
for pn,pref in enumerate(prefs):
    for cn,city in enumerate(pref):
        L = str(pn+1).zfill(6)
        R = str(cn+1).zfill(6)
        i = city[1]
        id_number = L+ R
        answers.append((i,id_number))
answers.sort()
for i,id_number in answers:
    print(id_number)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
PY=[]
for i in range(M):
    PY.append(list(map(int,input().split())))
    PY[i].append(i)
PY=sorted(PY,key=lambda x: x[1])
PY=sorted(PY,key=lambda x: x[0])

X=[1]
for i in range(1,M):
    if PY[i][0] == PY[i-1][0]:
        X.append(X[-1]+1)
    else:
        X.append(1)

for i in range(M):
    PY[i].append(str(PY[i][0]).rjust(6,'0')+\
              str(X[i]).rjust(6,'0'))

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

for i in range(M):
    print(PY[i][3])

Submission status: Accepted

Solution code:
import sys
from bisect import *
from collections import *
from copy import deepcopy
from datetime import *
from heapq import *
from itertools import *
# from math import *
from operator import *
from pprint import *

sys.setrecursionlimit(10**8)

input = sys.stdin.readline

def main():
    """ main """
    N,M = map(int, input().split())
    cities = [tuple(map(int, input().split())) for _ in range(M)]
    cities = [(pref,year,idx) for idx,(pref,year) in enumerate(cities)]
    cities.sort(key=itemgetter(1))
    cities.sort(key=itemgetter(0))
    prev_pref = 0
    tmp = 1
    res = [0]*M
    for pref,_,idx in cities:
        if prev_pref != pref:
            prev_pref = pref
            tmp = 1
        else:
            tmp += 1
        res[idx] = str(pref).zfill(6) + str(tmp).zfill(6)
    for r in res:
        print(r)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, m = (int(i) for i in input().split()) 
py = [[int(i) for i in input().split()] for i in range(m)]
cnt = [0]*(n+1)
ids = {}
for p,y in sorted(py, key=lambda x: x[1]):
  cnt[p] += 1
  ids[y] = '%06d%06d' % (p, cnt[p])
for _, y in py:
  print(ids[y])

Submission status: Accepted

Solution code:
import collections as coll
import bisect
n,m=map(int,input().split())
py=[list(map(int,input().split())) for _ in range(m)]
a=coll.defaultdict(list)
for x,y in sorted(py): a[x].append(y)
for x,y in py:
    z=bisect.bisect(a[x],y)
    print('%06d%06d'%(x,z))

Submission status: Accepted

Solution code:
N,M=list(map(int,input().split()))
pref=[[] for i in range(N)]
for i in range(M):
    P,Y=list(map(int,input().split()))
    pref[P-1].append((i+1,Y))
ans=['' for i in range(M)]
for i in range(N):
    arr=sorted(pref[i],key=lambda x:x[1])
    for j,x in enumerate(arr):
        ans[x[0]-1]='{0:06d}{1:06d}'.format(i+1,j+1)
for x in ans:
    print(x)

Submission status: Accepted

Solution code:
def fix(s):
  ss = str(s)
  while len(ss) < 6:
    ss = "0" + ss
  return ss

N, M = map(int, input().split())
PY = [(0,0,0)] * M
Num = [(0,0,0)] * M

for i in range (M):
    P, Y = map(int, input().split())
    PY[i] = (P, Y, i)
PY.sort()

for i in range (M):
  if PY[i-1][0] == PY[i][0]:
    Num[i] = (PY[i][2], PY[i][0], Num[i-1][2]+1)
  else:
    Num[i] = (PY[i][2], PY[i][0], 1)

Num.sort()
for i in range(M):
  print(fix(Num[i][1]) + fix(Num[i][2]))

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
pys = []
for i in range(m):
    pys.append([i+1])
    pys[i][len(pys[i]):len(pys[i])] = list(map(int,input().split()))

ms = []
for _ in range(n+1):
    ms.append([])

for py in pys:
    ms[py[1]].append(py)

for sm in ms:
    sm.sort(key=lambda x : x[2])
    for i in range(len(sm)):
        sm[i].append(i+1)


res = []
for _ in range(m+1):
    res.append([])

for m in ms:
    for shi in m:
        res[shi[0]]=[shi[1],shi[3]]

for i in range(1,len(res)):
    print(str(res[i][0]).zfill(6)+str(res[i][1]).zfill(6))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
city=[]
table={}
table2={}
for i in range(m):
    city.append(list(map(int,input().split())))
    word=str(city[i][0])+str(city[i][1])
    table[i]=word
city.sort()
temp=city[0][0]
count=1
for i in range(m):
    if temp!=city[i][0]:
        temp=city[i][0]
        count=1
    top=str(0)*(6-len(str(city[i][0])))+str(city[i][0])
    bottom=str(0)*(6-len(str(count)))+str(count)
    word=str(city[i][0])+str(city[i][1])
    table2[word]=top+bottom
    count+=1
for i in range(m):
    print(table2[table[i]])

Submission status: Accepted

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

s = []
o = {}
for i, (c,(d,b)) in enumerate(p):
    a = d
    if not a in o.keys():
        o[a] = 1
    else:
        o[a] += 1
    s.append([c, d, o[a]])

s.sort(key=lambda x: x[0])
for (a,b,c) in s:
    print("".join([str(b).zfill(6), str(c).zfill(6)]))

Submission status: Accepted

Solution code:
import sys
import os
from operator import itemgetter

N,M = map(int,input().split())
cities = [ 0 for _ in range(M) ]

for i in range(M):
    p,y = map(int,input().split())
    cities[i] = [p,y,i]
cities = sorted(cities,key=itemgetter(1))
cities = sorted(cities,key=itemgetter(0))

out = ["*" for _ in range(M)]
beforeCity = cities[0][0]
cityCnt = 1
for i in range(M):
    curCity = cities[i][0]
    if beforeCity != curCity:
        cityCnt = 1
    cityNo1 = str(curCity).zfill(6)
    cityNo2 = str(cityCnt).zfill(6)
    out[cities[i][2]] = cityNo1+cityNo2
    beforeCity = curCity
    cityCnt += 1

for a in out:
    print(a)

Submission status: Accepted

Solution code:
# ABC113C - ID
def main():
    N, M, *PY = map(int, open(0).read().split())
    P = [[] for _ in range(N + 1)]  # prefectures
    # classify cities by prefectures
    for num, (pref, year) in enumerate(zip(*[iter(PY)] * 2)):
        P[pref] += [(year, num)]
    ans = [[] for _ in range(M)]
    P = [sorted(p) for p in P]  # sort by year
    for pref_idx, pref in enumerate(P):
        for city_idx, (_, num) in enumerate(pref, 1):
            x = "{:06}{:06}".format(pref_idx, city_idx)
            ans[num] = x
    print("\n".join(map(str, ans)))

    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC113C - ID
def main():
    N, M, *PY = map(int, open(0).read().split())
    P = [[] for _ in range(N + 1)]  # prefectures
    # classify cities by prefectures
    for num, (pref, year) in enumerate(zip(*[iter(PY)] * 2)):
        P[pref] += [(year, num)]
    ans = [""] * M
    P = [sorted(p) for p in P]  # sort by year
    for pref_idx, pref in enumerate(P):
        for city_idx, (_, num) in enumerate(pref, 1):
            x = "{:06}{:06}".format(pref_idx, city_idx)
            ans[num] = x
    print("\n".join(map(str, ans)))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from bisect import bisect_left
from collections import defaultdict
n, m = map(int, input().split())
m = [tuple(map(int, input().split())) for _ in range(m)]

d = defaultdict(list)
for p, y in sorted(m):
    d[p].append(y)

for p, y in m:
    print('{:06}{:06}'.format(p, bisect_left(d[p], y)+1))

Submission status: Accepted

Solution code:
from bisect import bisect_left
from collections import defaultdict
n, m = map(int, input().split())
m = [tuple(map(int, input().split())) for _ in range(m)]

d = defaultdict(list)
for p, y in sorted(m):
    d[p] += [y]


for p, y in m:
    i = bisect_left(d[p], y)
    print('{:06}{:06}'.format(p, i+1))

Submission status: Accepted

Solution code:
from collections import defaultdict
import bisect

n, m = map(int,input().split())
a = [list(map(int,input().split())) for i in range(m)]

d = defaultdict(list)
for i in sorted(a):
    d[i[0]].append(i[1])

for x,y in a:
    print(str(x).zfill(6) + str(bisect.bisect_left(d[x], y)+1).zfill(6))

Submission status: Accepted

Solution code:
import sys


class City:
    def __init__(self, ind, pref, time):
        self.ind = ind
        self.pref = pref
        self.time = time
        self.sort_res = None

    def get_id(self):
        str1 = "0" * (6 - len(str(self.pref))) + str(self.pref)
        str2 = "0" * (6 - len(str(self.sort_res))) + str(self.sort_res)
        return str1 + str2
    def __str__(self):
    	return str(self.ind)
if __name__ == '__main__':
    nm = list(sys.stdin.readline().split(" "))
    N = int(nm[0])
    M = int(nm[1])
    prefs = [[] for x in range(N)]
    cities = []
    for i in range(M):
        info = sys.stdin.readline().rstrip().split(" ")
        newcity = City(i, int(info[0]), int(info[1]))
        prefs[int(info[0])-1].append(newcity)
    for i in range(N):
        prefs[i].sort(key=lambda x: x.time)
        for j in range(len(prefs[i])):
            prefs[i][j].sort_res = j + 1
    for i in prefs:
        for j in i:
            cities.append(j)
    cities.sort(key=lambda y: y.ind)
    for i in cities:
        print(i.get_id())

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n,m = map(int, input().split())
i=0
lst = []
while i < m: 
    lst.append(list(map(int, input().split())) + [i])
    i+=1
lst = sorted(lst)
j=0
i=1
for k in lst:
    if i != k[0]:
        i=k[0]
        j=1
        k[1]=i*1000000+j
    else:
        j+=1
        k[1]=i*1000000+j

#ans
for ans in sorted(lst, key=lambda x:x[2]):
    print('{0:012d}'.format(ans[1]))

Submission status: Accepted

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

ans = [''] * m

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

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


lc = 0
pref_count = 0
city_count = 0
for i in range(m):
    c = cities_sorted[i]

    if c[0] != lc:
        lc = c[0]
        pref_count += 1
        city_count = 0

    city_count += 1

    ans[c[2]] = str(c[0]).zfill(6) + str(city_count).zfill(6)

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

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((p,y,i))
py.sort()
li = [[0]*2 for i in range(m)]
s = 0
t = 0
for p,y,i in py:
    #もしs!=pならその県は初めてなので1番目、違うならそこから+1
    if s != p:
        s = p
        t = 1
    else:
        t += 1
    li[i][0] = s
    li[i][1] = t
for i in range(m):
    print(str(li[i][0]).zfill(6) + str(li[i][1]).zfill(6))

Submission status: Accepted

Solution code:
import numpy as np
N, M=map(int, input().split())
PY=np.array([list(map(int, input().split()))+[i] for i in range(M)])
PY=PY[np.argsort(PY[:, 1])]
kenorder=[1]*(N+1)
output=[0]*M
temporder=[0]*M
for i in range(M):
  temp=PY[i, :]
  a='{:06d}'.format(temp[0])
  b='{:06d}'.format(kenorder[temp[0]])
  output[i]=a+b
  temporder[i]=temp[2]
  kenorder[temp[0]]+=1
  
output2=[0]*M
for i in range(M):
  output2[temporder[i]]=output[i]

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

Submission status: Accepted

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


def main():
    N, M = map(int, input().split())
    A = [[] for _ in range(N)]
    for i in range(M):
        p, y = map(int, input().split())
        A[p-1].append([y, i])
    
    B = ['']*M
    for i in range(N):
        if len(A[i])==0:
            continue
        A[i].sort()
        for j in range(len(A[i])):
            S = str(i+1).zfill(6) + str(j+1).zfill(6)
            B[A[i][j][1]] = S
    
    for i in range(M):
        print(B[i])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
import heapq
n_pref, m_city = list(map(int, input().split()))
record = defaultdict(list)
cities = []
for i in range(m_city):
  pref, year = list(map(int, input().split()))
  cities.append({"pref": pref, "year": year})
  heapq.heappush(record[pref], year)
res = defaultdict(dict)
for key ,value in record.items():
  for i in range(1, len(value) + 1):
    res[key][heapq.heappop(value)] = i
for city in cities:
  print(format(city["pref"], '06d'), format(res[city["pref"]][city["year"]], '06d'), sep="")

Submission status: Accepted

Solution code:
ken_num, city_num = map(int,input().split())
city_list = [None for _ in range(city_num)]
ken_list = [1 for _ in range(ken_num+1)]
id_list = [None for _ in range(city_num)]
for index in range(city_num):
    city_list[index] = list(map(int,input().split()))
    city_list[index].append(index)
city_list = sorted(city_list, key=lambda x: x[1])

for index,city in enumerate(city_list):
    id_list[city[2]] = str(city[0]).zfill(6) + str(ken_list[city[0]]).zfill(6)
    ken_list[city[0]] += 1

for ans in id_list:
    print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
LPY = []
for i in range(M):
    p, y = map(int, input().split())
    LPY.append([i, p, y]) # ラベル,県,年

# 県,年を県優先でソート
LPY = sorted(LPY, key=lambda x:(x[1], x[2]))

# xを追加
x = 1
for i in range(M-1):
    LPY[i].append(x)
    if LPY[i][1] == LPY[i+1][1]:
        x += 1
    else:
        x = 1
LPY[M-1].append(x)

# LPYを元にラベルと番号のリストを作成
ans = []
for i in range(M):
    label = LPY[i][0]
    p = LPY[i][1]
    x = LPY[i][3]
    num = "{0:06d}".format(p) + "{0:06d}".format(x)
    ans.append([label, num])

# ラベル順にソート
ans.sort()

# 出力
for i in range(M):
    print(ans[i][1])

Submission status: Accepted

Solution code:
N, M = list(map(int, input().split()))
PY = []
for i in range(M):
    p, y = list(map(int, input().split()))
    PY.append([p, y, i, 0])
PY.sort(key=lambda x:(x[0], x[1]))

city = PY[0][0]
city_start = 0
for i in range(len(PY)):
    if city == PY[i][0]:
        city_start += 1
    else:
        city = PY[i][0]
        city_start = 1
    PY[i][3] = str(city).zfill(6) + str(city_start).zfill(6)

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

Submission status: Accepted

Solution code:
from operator import itemgetter
n, m = map(int, input().split())
cities = []
for i in range(1, m + 1):
    p, y = map(int, input().split())
    cities.append([i, p, y])
cities.sort(key=itemgetter(2))
cities.sort(key=itemgetter(1))

prefNo = 0
for city in cities:
    if prefNo != city[1]:
        prefNo = city[1]
        seq = 0
    seq += 1
    city.append(seq)
cities.sort()
for city in cities:
    print(str(city[1]).zfill(6) + str(city[3]).zfill(6))

Submission status: Accepted

Solution code:

def solve():
  n,m = (int(i) for i in input().split())
  query = [[] for _ in range(n)]
  ans = ["0"]*m
  for si in range(m):
    p,y = (int(i) for i in input().split())
    query[p-1].append((y,si))
  for i in range(n):
    query[i] = sorted(query[i])
    tp = len(query[i])
    si = "0"*(6-len(str(i+1)))+str(i+1)
    if query[i]:
      for year in range(tp):
        gomi,number = query[i][year] 
        d = "0"*(6-len(str(year+1)))+str(year+1)
        ans[number] = si+d
  for i in range(m):
    print(ans[i])

solve()

Submission status: Accepted

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

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

somelists.sort(key=lambda x:(x[1],x[2]))

prefs=1
numbers=0

for x in somelists:
    
    if x[1]==prefs:
        numbers+=1
        
        x.append(numbers)
    if x[1]!=prefs:
        prefs=x[1]
        numbers=1
        x.append(numbers)

somelists.sort(key=lambda x:x[0])
for _ in range(m):
    print(str(somelists[_][1]).zfill(6)+str(somelists[_][3]).zfill(6))

Submission status: Accepted

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

for i in range(M):
    PY[i].append(i)

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

prefecture = 0
cnt = 1
for i in range(M):
    if prefecture != PY[i][0]:
        prefecture = PY[i][0]
        cnt = 1
    else:
        cnt += 1
    PY[i].append(cnt)

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

for i in range(M):
    print('{:06}{:06}'.format(PY[i][0], PY[i][3]))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
lis=[]
for i in range(m):
    lis.append(list(map(int,input().split())))
    lis[i].append(i)
lis.sort()
lis[0][1]=1
for i in range(m-1):
    if lis[i][0]==lis[i+1][0]:
        lis[i+1][1]=lis[i][1]+1
    else:
        lis[i+1][1]=1
for i in range(m):
    lis[i].append(str(lis[i][0]).rjust(6,"0")+str(lis[i][1]).rjust(6,"0"))
    del lis[i][0]
    del lis[i][0]
lis.sort()
for i in range(m):
    print(lis[i][1])

Submission status: Accepted

Solution code:
from collections import defaultdict
if __name__ == '__main__':
    N, M = map(int, input().split())
    PY = [0]*M
    ID = [0]*M
    for i in range(M):
        PY[i] = list(map(int, input().split()))
        PY[i].append(i)
    
    PY.sort(key=lambda x: x[1])
    count = defaultdict(int)
    for i in range(M):
        count[PY[i][0]] += 1
        ID[i] = [str(PY[i][0]).zfill(6) + str(count[PY[i][0]]).zfill(6), PY[i][2]]
    ID.sort(key=lambda x: x[1])
    for i in range(M):
        print(ID[i][0])

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
G = {}
for i in range(M):
    P,Y = map(int,input().split())
    if P not in G:
        G[P]=[]
    G[P].append((i+1,Y))
C = []
for P in G:
    G[P] = sorted(G[P],key=lambda x:x[1])
    a = len(str(P))
    x = "0"*(6-a)+str(P)
    for i in range(len(G[P])):
        b = len(str(i+1))
        y = x+"0"*(6-b)+str(i+1)
        C.append((G[P][i][0],y))
C = sorted(C,key=lambda x:x[0])
for c in C:
    print(c[1])

Submission status: Accepted

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

def main():
    n, m = map(int, input().split())
    A = [list(map(int, input().split())) + [i] for i in range(m)]
    B = [''] * m
    A.sort()
    count = 0
    i, x = 1, 1
    for a in A:
        if a[0] == i:
            B[a[2]] = '{:06}{:06}'.format(a[0], x)
        else:
            i, x = a[0], 1
            B[a[2]] = '{:06}{:06}'.format(a[0], x)
        x += 1
    print('\n'.join(B))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

def main():
    n, m = map(int, input().split())
    A = []
    B = [''] * m
    for i in range(m):
        p, y = map(int, input().split())
        A.append((p, y, i))
    A.sort()
    count = 0
    i, x = 1, 1
    for a in A:
        if a[0] == i:
            B[a[2]] = '{:06}{:06}'.format(a[0], x)
        else:
            i, x = a[0], 1
            B[a[2]] = '{:06}{:06}'.format(a[0], x)
        x += 1
    print('\n'.join(B))


if __name__ == '__main__':
    main()