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: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
pys = [list(map(int, input().split())) for _ in range(m)]
d = [[] for _ in range(n)]
for py in pys:
    p, y = py
    d[p - 1].append(y)

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

for py in pys:
    p, y = py
    number = d[p - 1].index(y) + 1

    print(str(p).zfill(6) + str(number).zfill(6))

Submission status: Time Limit Exceeded

Solution code:
a = input().split()
a = [int(i) for i in a]
query = []
citydict = dict()
for i in range(a[1]):
	temp = input().split()
	temp = [int(i) for i in temp]
	query.append(temp)
	if temp[0] not in citydict:
		citydict[temp[0]] = [temp[1]]
	else:
		citydict[temp[0]].append(temp[1])
		
for i in citydict:
	citydict[i] = sorted(citydict[i])
	
for i in query:
	print ("%06d%06d" % (i[0],citydict[i[0]].index(i[1]) + 1))

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int,input().split())
dic = {}
P = []; Y = []
for i in range(M):
    p, y = map(int,input().split())
    P.append(p)
    Y.append(y)
    if p not in dic:
        dic[p] = [y]
    else:
        dic[p].append(y)

for p in dic.values():
    p.sort()

for i in range(M):
    print("{:06d}{:06d}".format(P[i], dic[P[i]].index(Y[i])+1))

Submission status: Time Limit Exceeded

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10**5)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n,m = li()
py = []
for _ in range(m):
    py.append(list(li()))

order = [[] for _ in range(n+1)]

for p,y in sorted(py, key=lambda x:x[1]):
    order[p].append(y)

cnt = [0]*(n+1)

for p,y in py:
    cnt[p] += 1
    ans = str(p).zfill(6) + str(order[p].index(y)+1).zfill(6)
    print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import bisect
N,M = map(int, input().split())
dic = defaultdict(list)
cities = []
for _ in range(M):
  p,y = map(int,input().split())
  cities.append([p,y])
for item in sorted(cities):
  dic[item[0]].append(item[1])
for item in cities:
  print("%06d%06d"%(item[0],bisect.bisect(dic[item[0]],item[1])))

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([i, p, y])
cnt = [0] * (n + 1)

sorted_py = sorted(py, key = lambda x: (x[1], x[2]))
for i in range(m):
    cnt[sorted_py[i][1]] += 1
    city_id = str(sorted_py[i][1]).zfill(6)+str(cnt[sorted_py[i][1]]).zfill(6)
    sorted_py[i].append(city_id)

sorted_py = sorted(sorted_py, key = lambda x: x[0])
for i in range(m):
    print(sorted_py[i][3])

Submission status: Accepted

Solution code:
from collections import defaultdict

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

for p in prefecture:
    if len(p)>=2:
        p.sort()

d = defaultdict(list)
for idx, pre in enumerate(prefecture):
    if len(pre)>=1:
        for i, year in enumerate(pre):
            d[(idx, year)]=[idx, i+1]

for tpl in tpl_lst:
    id = d[tpl][0]*(10**6) + d[tpl][1]
    id = str(id)
    id = "0"*(12-len(id)) + id
    print(id)
#print(prefecture)

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,0])
from operator import*
l.sort(key=itemgetter(2))
P=[0]*N
for i in range(M):P[l[i][1]-1]+=1;l[i][3]=P[l[i][1]-1]
l.sort(key=itemgetter(0))
for i in range(M):print(str(l[i][1]).zfill(6)+str(l[i][3]).zfill(6))

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    N, M = map(int, input().split())
    PY = []
    for i in range(1, M+1):
        p, y = map(int, input().split())
        PY.append((y, p, i))
    PY.sort()
    ANS = [""]*(M+1)
    P = [0]*(N+1)
    for y, p, i in PY:
        P[p] += 1
        ANS[i] = "{0:06d}".format(p) + "{0:06d}".format(P[p])
    
    for ans in ANS:
        if ans=="": continue
        print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A = []
B = [[] for i in range(N)]
for i in range(M):
  P, Y = map(int, input().split())
  A.append([P, Y])
  B[P-1].append(Y)
for i in range(N):
  B[i].sort()
d = {}
for i in range(N):
  for y in range(len(B[i])):
    d[(i+1, B[i][y])] = y + 1
for i in range(M):
  print('{:0=6}'.format(A[i][0]) + '{:0=6}'.format(d[(A[i][0], A[i][1])]))

Submission status: Accepted

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

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

    inlis = sorted(inlis, key = lambda x:x[2])
    anslis = []
    tmpdic = dict()

    for i in range(m):
        j, p, y = inlis[i][0], inlis[i][1], inlis[i][2]
        
        if p not in tmpdic:
            tmpdic[p] = 1
        else:
            tmpdic[p] += 1
        
        num = str(tmpdic[p]).zfill(6)
        ken = str(p).zfill(6)

        ans = ken + num
        anslis.append([j,ans])
    
    anslis = sorted(anslis, key = lambda x:x[0])

    for [city, num] in anslis:
        print(num)


    



if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

Z = zip(P, Y, I)
Z = sorted(Z)
P, Y, I = zip(*Z)

N = []
c = P[0]
d = 1
for i in range(m):
    if c == P[i]:
        N.append("{0:06d}{1:06d}".format(c, d))
        d += 1
    else:
        c = P[i]
        d = 1
        N.append("{0:06d}{1:06d}".format(c, d))
        d += 1

Z = zip(I, N)
Z = sorted(Z)
I, N = zip(*Z)
for i in N:
    print(i)

Submission status: Accepted

Solution code:
import bisect
n,m = map(int,input().split())
x = [list() for i in range(n)]
p = []
y = []
for i in range(m):
  s,t = map(int,input().split())
  p.append(s)
  y.append(t)
  x[s-1].append(t)
for i in range(n):
  x[i].sort()
  
for i in range(m):
  index = bisect.bisect_left(x[p[i]-1],y[i])
  print("{:06}{:06}".format(p[i],index+1))

Submission status: Accepted

Solution code:
import bisect

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

ans=[]

re=[[] for _ in range(n)]



for _ in range(m):
  a=list(map(int,input().split()))
  re[a[0]-1].append(a[1])
  ans.append(a)
  
d=[]
for f in re:
  sor=[]
  
  new=sorted(list(set(f)))
  
  for i in f:
    c=bisect.bisect_left(new,i)
    sor.append(c+1)
    
  d.append(sor)
    
  
for x in ans:
  p=x[0]
  q=d[p-1].pop(0)
  print(str('{:0=6}'.format(p))+str('{:0=6}'.format(q)))

Submission status: Accepted

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

ans=[""]*M
A=sorted(A, key=lambda x: x[1])
A=sorted(A,key=lambda x:x[0])

now=A[0][0]
cnt=1
for i in range(M):
    pref=str(A[i][0])
    
    if A[i][0]!=now:
        cnt=1
    year=str(cnt)
    now=A[i][0]
    cnt+=1

    ans[A[i][2]]=pref.zfill(6)+year.zfill(6)

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

Submission status: Accepted

Solution code:
# import sys
# sys.setrecursionlimit(10 ** 6)
# import bisect
# from collections import deque
# from decorator import stop_watch
#
#
# @stop_watch
def solve(N, M, PY):
    ken = [0] * (N + 1)
    PY = [PY[i] + [i] for i in range(M)]
    PY.sort(key=lambda x: x[1])
    for i in range(M):
        p, y, s = PY[i]
        ken[p] += 1
        PY[i].append(ken[p])
    PY.sort(key=lambda x: x[2])
    for p, y, s, n in PY:
        print(('000000' + str(p))[-6:] + ('000000' + str(n))[-6:])


if __name__ == '__main__':
    N, M = map(int, input().split())
    PY = [[int(i) for i in input().split()] for _ in range(M)]
    solve(N, M, PY)

    # # test
    # from random import randint, sample
    # from func import random_str
    # N, M = 10 ** 5, 10 ** 5
    # PY = sample([[randint(1, 5), 10 ** 8 - i] for i in range(M)], M)
    # solve(N, M, PY)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
PY=[[list(map(int,input().split())),i] for i in range(M)]
PY.sort()
cnt=[0 for i in range(N+1)]
ans=[]
for i in range(M):
    cnt[PY[i][0][0]]+=1
    ans.append([PY[i][1],str(PY[i][0][0]).zfill(6)+str(cnt[PY[i][0][0]]).zfill(6)])
ans.sort()
for i in range(M):
    print(ans[i][1])

Submission status: Accepted

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

ans=[]

re=[[] for _ in range(n)]



for _ in range(m):
  a=list(map(int,input().split()))
  re[a[0]-1].append(a[1])
  ans.append(a)
  
d={}
for f in re:
  new=sorted(f)
  
  for i in range(len(new)):
    d[new[i]]=i+1
  
for x in ans:
  p=x[0]
  q=d[x[1]]
  print(str('{:0=6}'.format(p))+str('{:0=6}'.format(q)))

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
py = [list(map(int,input().split()))+[i] for i in range(M)]
py.sort()
P = py[0][0]
c = 0
ans = []
for p,y,i in py:
    if p == P:
        c += 1
    else:
        P = p
        c = 1
    ansc = str(c)
    ansp = str(p)
    anser = "0" * (6-len(ansp)) + ansp + "0" *(6-len(ansc)) + ansc
    ans.append([i,anser])
ans.sort()
for i,anser in ans:
    print(anser)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import collections
import 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:
def main():
    # n = int(input())
    n, m = map(int, input().split())
    # v = list(map(int, input().split()))
    # s = input()
    py = []
    for i in range(m):
        p, y = map(int, input().split())
        py.append([i, p, y])

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

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

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

    for i in range(m):
        print(str(py[i][1]).zfill(6) + str(py[i][3]).zfill(6))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

PY.sort(key=lambda x:x[1])
ans = []
cnt = [0] * N
for p, y, i in PY:
  ans.append(("{0:06d}".format(p)+"{0:06d}".format(cnt[p-1]+1), i))
  cnt[p-1] += 1
ans.sort(key=lambda x:x[1])
for a in ans:
  print(a[0])

Submission status: Accepted

Solution code:
from bisect import bisect_right
n, m = map(int, input().split())
py = [tuple(map(int, input().split())) for _ in range(m)]
d = dict()
for p, y in py:
    if p not in d.keys():
        d[p] = [y]
    else:
        d[p].append(y)

for v in d.values():
    v.sort()

for p, y in py:
    print(str(p).zfill(6) + str(bisect_right(d[p], y)).zfill(6))

Submission status: Accepted

Solution code:
import bisect, copy, heapq, math, sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
def celi(a,b):
    return -(-a//b)
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

py.sort()
anslst=[""]*m
dic=defaultdict(int)

for i in range(m):
    p,y,index=py[i]
    dic[p]+=1
    pnum=str(p)
    pnum="0"*(6-len(pnum))+pnum
    ynum=str(dic[p])
    ynum="0"*(6-len(ynum))+ynum
    anslst[index]=pnum+ynum
for i in range(m):
    print(anslst[i])

Submission status: Accepted

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

C = []
for i in range(M):
    p, y = map(int, input().split())
    C.append([i, p, y])
C.sort(key=lambda x: (x[1], x[2]))

ans = []
k = C[0][1]
n = 1
for i in range(M):
    city = C[i][1]
    if k != city:
        k = city
        n = 1
    number = f'{city:06}{n:06}'
    ans.append([C[i][0], number])
    n += 1
ans.sort(key=lambda x: x[0])
for i in range(M):
    print(ans[i][1])

Submission status: Accepted

Solution code:
import math
from math import gcd,pi,sqrt
INF = float("inf")

import sys
sys.setrecursionlimit(10**6)
import itertools
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]

def main():
    n,m = i_map()
    l = []
    for i in range(m):
        p,y = i_map()
        l.append([i,p,y,0])

    l.sort(key = lambda x :(x[1], x[2]))
    ken = l[0][1]
    cnt = 1

    for i in l:
        if i[1] == ken:
            i[3] = cnt
            cnt += 1
        else:
            i[3] = 1
            cnt = 2
            ken = i[1]
    l.sort(key = lambda x:x[0])

    ans = []
    for i in l:
        ans.append(str(i[1]).zfill(6) + str(i[3]).zfill(6))
    for i in ans:
        print(i)

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def main():
    n, m= LI()
    dic = collections.defaultdict(list)
    ans_lst = []

    for i in range(m):
        p, y = LI()
        dic[p].append((i, y))

    for key in dic.keys():
        dic[key].sort(key=lambda x: x[1])
        pfil = str(key).zfill(6)

        for i in range(len(dic[key])):
            id = pfil + str(i+1).zfill(6)
            ans_lst.append((dic[key][i][0], id))

    ans_lst.sort()
    ans = list(zip(*ans_lst))[1]
    print(*ans,sep="\n")
main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Tue Sep 15 01:01:58 2020

@author: liang
"""
#ゼロパディング＋インデックス
#str(1).zfill(6) + str(a.index(2) + 1).zfill(6)
#index(x) が重い => indexを使わなくて良いようにする

N, M = map(int, input().split())
#d = [list() for _ in range(N)]
dic = dict()
dic2 = dict()
P = list()

#insert O(M)
for i in range(M):
    p, y = map(int,input().split())
    #d[p-1].append(y)
    if p not in dic.keys():
        dic[p] = [y]
    else:
        dic[p].append(y)
    P.append((p,y))

#year sort O(N log N) => 重い　dict使用
#for i in range(N):
#    d[i].sort()
for key in dic.keys():
    dic[key].sort()

for key in dic.keys():
    for i in range(len(dic[key])):
        dic2[dic[key][i]] = i+1
#search O(M)***
for i in range(M):
    p, y = P[i]
    ans = str(p).zfill(6)+str(dic2[y]).zfill(6)
    """
    # zfill 重い？
    ans = ''
    ans += '0'*( 6 - len(str(p))) + str(p)
    #t = dic[p].index(y)+1
    t = dic2[y]
    ans += '0'*( 6 - len(str(t))) + str(t)
    """
    print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Tue Sep 15 01:01:58 2020

@author: liang
"""
#ゼロパディング＋インデックス
#str(1).zfill(6) + str(a.index(2) + 1).zfill(6)
#index(x) が重い => indexを使わなくて良いようにする

N, M = map(int, input().split())
#d = [list() for _ in range(N)]
dic = dict()
dic2 = dict()
P = list()

#insert O(M)
for i in range(M):
    p, y = map(int,input().split())
    #d[p-1].append(y)
    if p not in dic.keys():
        dic[p] = [y]
    else:
        dic[p].append(y)
    P.append((p,y))

#year sort O(N log N) => 重い　dict使用
#for i in range(N):
#    d[i].sort()
for key in dic.keys():
    dic[key].sort()

for key in dic.keys():
    for i in range(len(dic[key])):
        dic2[dic[key][i]] = i+1
#search O(M)***
for i in range(M):
    p, y = P[i]
    #ans = str(p).zfill(6)+str(d[p-1].index(y)+1).zfill(6)
    # zfill 重い？
    ans = ''
    ans += '0'*( 6 - len(str(p))) + str(p)
    #t = dic[p].index(y)+1
    t = dic2[y]
    ans += '0'*( 6 - len(str(t))) + str(t)
    print(ans)

Submission status: Accepted

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


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


for i in range(N):
    keep[i] = sorted(keep[i], key=lambda x: x[2])

for i in range(N):
    biggest = len(keep[i])
    j = 0
    while j < biggest:
        keep[i][j][2] = j + 1
        j += 1
    keep2 += keep[i]

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

for i in range(M):
    ans = ''
    ans += '0' * (6 - len(str(keep2[i][1]))) + str(keep2[i][1])
    ans += '0' * (6 - len(str(keep2[i][2]))) + str(keep2[i][2])
    print(ans)

Submission status: Accepted

Solution code:
import bisect

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

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

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

for i,v in x:
    lst[i-1].append(v)

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

for i,v in x:
    z=bisect.bisect_left(lst[i-1],v)+1

    print('0'*(6-len(str(i)))+str(i)+'0'*(6-len(str(z)))+str(z))

Submission status: Accepted

Solution code:
import bisect

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

Q = []
P = [[] for _ in range(n)]
for i in range(m):
    p,y = map(int,input().split())
    Q.append([p,y])
    P[p-1].append(y)

P_1 = [sorted(l) for l in P]

for p,y in Q:
    a = str(p).zfill(6)
    b = str(bisect.bisect(P_1[p-1], y)).zfill(6)
    print(a+b)

Submission status: Accepted

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

def main():
    n, m = map(int, input().split())

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

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

    ans = [('', '')] * m
    cnt = [1] * n
    for y, p, i in yp:
        ans[i] = (str(p+1), str(cnt[p]))
        cnt[p] += 1

    for i, j in ans:
        print('0' * (6 - len(i)) + i + '0' * (6 - len(j)) + j)

main()

Submission status: Accepted

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

sortPY = sorted(PY, key=lambda x: x[1])
prefec = [0]*(N+1)
res = []
for p, y, i in sortPY:
    prefec[p] += 1
    strp = str(p)
    ID = '0'*(6-len(strp)) + strp + '0'*(6-len(str(prefec[p]))) + str(prefec[p])
    res.append([ID, i])

sortres = sorted(res, key=lambda x: x[1])
for i in range(M):
    print(sortres[i][0])

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
d={}
PY=[]
import bisect
for _ in range(M):
    p,y=map(int,input().split())
    PY.append((p,y))
    t=d.get(p, [0])
    i=bisect.bisect_left(t,y)
    t.insert(i,y)
    d[p]=t
    
dx={}
for k, v in d.items():
    for i in range(len(v)):
        dx[(k,v[i])]=i
        
for p,y in PY:
    print(str(p).zfill(6)+str(dx[(p,y)]).zfill(6))

Submission status: Accepted

Solution code:

url = "https://atcoder.jp//contests/abc113/tasks/abc113_c"

def main():
    t = list(map(int, input().split()))
    town = {k: [] for k in range(1, t[0]+1)}
    all_town = []
    for _ in range(t[1]):
        tmp = list(map(int, input().split()))
        all_town.append(tmp)
        town[tmp[0]].append(tmp[1])
    ans = {}
    for k in town:
        town[k].sort()
        tmp_dic = {town[k][i]: str(k).zfill(6)+str(i+1).zfill(6) for i in range(len(town[k]))}
        ans.update(tmp_dic)
    for at in all_town:
        print(ans[at[1]])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from sys import exit
from collections import deque
from bisect import bisect_left, bisect_right, insort_left, insort_right
from heapq import heapify, heappop, heappush
from itertools import product, permutations, combinations, combinations_with_replacement
from functools import reduce
from math import gcd, sin, cos, tan, asin, acos, atan, degrees, radians

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def lgcd(l):
    return reduce(gcd,l)
def llcm(l):
    return reduce(lcm,l)
def powmod(n,i,mod):
    return pow(n,mod-1+i,mod) if i<0 else pow(n,i,mod)
def div2(x):
    return x.bit_length()
def div10(x):
    return len(str(x))-(x==0)
def perm(n,mod=None):
    ans = 1
    for i in range(1,n+1):
        ans *= i
        if mod!=None:
            ans %= mod
    return ans
def intput():
    return int(input())
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x,d=1):
        self.setdefault(x,0)
        self[x] += d
    def list(self):
        l = []
        for k in self:
            l.extend([k]*self[k])
        return l
class comb():
    def __init__(self, n, mod=None):
        self.l = [1]
        self.n = n
        self.mod = mod
    def get(self,k):
        l,n,mod = self.l, self.n, self.mod
        k = n-k if k>n//2 else k
        while len(l)<=k:
            i = len(l)
            l.append(l[i-1]*(n+1-i)//i if mod==None else (l[i-1]*(n+1-i)*powmod(i,-1,mod))%mod)
        return l[k]
def pf(x):
    C = counter()
    p = 2
    while x>1:
        k = 0
        while x%p==0:
            x //= p
            k += 1
        if k>0:
            C.add(p,k)
        p = p+2-(p==2) if p*p<x else x
    return C

def f(x):
    return '0'*(6-div10(x))+str(x)

N,M=mint()
S=dict()
for i in range(M):
    p,y=mint()
    S.setdefault(p,[])
    S[p].append((y,i))
ans=[0]*M
for p in S:
    S[p].sort()
    for j in range(len(S[p])):
        y,i=S[p][j]
        ans[i]=f(p)+f(j+1)
lprint(ans)

Submission status: Accepted

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

ids=["" for i in range(m)]
for i in range(n):
  l[i].sort()
  for j in range(len(l[i])):
    ids[l[i][j][1]]="{:0>6d}".format(i+1)+"{:0>6d}".format(j+1)
print("\n".join(ids))

Submission status: Accepted

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

p_dict = {}

for i in range(M):
  p, y = map(int, input().split())
  if p not in p_dict.keys():
    p_dict[p] = [[y, p, i]]
  else:
    p_dict[p].append([y, p, i])
  
ans = []
for p in p_dict.keys():
  p_dict[p].sort()
  for i in range(len(p_dict[p])):
    p_dict[p][i].append(i + 1)
    ans.append(p_dict[p][i])
    
ans.sort(key=lambda x: x[2])
for y, p, oi, si in ans:
  print("{:06d}{:06d}".format(p, si))

Submission status: Accepted

Solution code:
import bisect
n,m = map(int,input().split())
x = [list() for i in range(n)]
p = []
y = []
for i in range(m):
  s,t = map(int,input().split())
  p.append(s)
  y.append(t)
  x[s-1].append(t)
for i in range(n):
  x[i].sort()
  
for i in range(m):
  index = bisect.bisect_left(x[p[i]-1],y[i])
  print("{:06}{:06}".format(p[i],index+1))

Submission status: Accepted

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

for i in range(m):
    p, y = map(int,input().split())
    numbers[p-1][i] = y #pで県を指定して、iで順番の情報を保つ

answers = {}

for i in range(n):
    number = numbers[i]
    if len(number) == 0:
        continue
    new_number = sorted(number.items(), key = lambda x : x[1]) #x[1]で誕生ねんでソート
    cnt = 1
    for num in new_number:
        answers[num[0]] = (6-len(str(i+1)))*'0' + str(i+1) + (6-len(str(cnt)))*'0' + str(cnt)
        cnt += 1

answer = sorted(answers.items(), key = lambda x : x[0])

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

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
numbers=[{} for n in range(N)]
for m in range(M):
    P,Y=map(int,input().split())
    numbers[P-1][m]=Y
answers={}
for n in range(N):
    number=numbers[n]
    if len(number)==0:
        continue
    new_number=sorted(number.items(), key=lambda x:x[1])
    suuji=1
    for num in new_number:
        answers[num[0]]=(6-len(str(n+1)))*'0'+str(n+1)+(6-len(str(suuji)))*'0'+str(suuji)
        suuji+=1
answer=sorted(answers.items(), key=lambda x:x[0])
for ans in answer:
    print(ans[1])

Submission status: Accepted

Solution code:
def make_code(prifacture_num, city_num):
    s1 = str(prifacture_num)
    while len(s1) != 6:
        s1 = '0' + s1
    s2 = str(city_num)
    while len(s2) != 6:
        s2 = '0' + s2
    return s1 + s2


prifacture_cnt, city_cnt = map(int, input().split())
data = [list(map(int, input().split())) for i in range(city_cnt)]
city_data = []

for i in range(city_cnt):
    city_data.append([data[i][0], data[i][1], i])

city_data.sort()
city_code = []
prifacture = city_data[0][0]
cnt = 0
for city in city_data:
    if prifacture == city[0]:
        cnt+=1
        s = make_code(prifacture, cnt)
        city_code.append([city[2], s])
    else:
        cnt = 1
        prifacture = city[0]
        s = make_code(prifacture, cnt)
        city_code.append([city[2], s])

city_code.sort()
for num,code in city_code:
    print(code)

Submission status: Accepted

Solution code:
class Info:
  def __init__(self, num, p, y, id):
    self.num = num
    self.p = p
    self.y = y
    self.id = id
    
n, m = map(int, input().split())
info = [Info(0, 0, 0, '')]
for num in range(1, m + 1):
  p, y = map(int, input().split())
  info.append(Info(num, p, y, ''))

info = sorted(info, key=lambda x: (x.p, x.y))

cnt = 1
for i in range(1, m + 1):
  if info[i].p != info[i-1].p:
    cnt = 1
  else:
    cnt += 1
  info[i].id = "{0:06d}{1:06d}".format(info[i].p, cnt)

info = sorted(info, key=lambda x: x.num)
info.pop(0)

for x in info:
  print(x.id)

Submission status: Accepted

Solution code:
import bisect

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

N, M = cin()
l1 = [[] for i in range(N + 1)]
l2 = []
for i in range(M):
    in1, in2 = cin()
    l1[in1].append(in2)
    l2.append([in1, in2])

for i in range(N + 1):  l1[i] = sorted(l1[i])
    
for i in range(M):
    c = l2[i]
    n = bisect.bisect_left(l1[c[0]], c[1]) + 1
    ans = str(c[0]).zfill(6) + str(n).zfill(6)
    print(ans)

Submission status: Accepted

Solution code:
# coding=utf-8
from math import floor, ceil, sqrt, factorial, log, gcd
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict
from heapq import heappop, heappush, heappushpop, heapify
import copy
import numpy as np
import sys
INF = float('inf')
mod = 10**9+7
sys.setrecursionlimit(10 ** 6)


def lcm(a, b): return a * b / gcd(a, b)

# 1 2 3
# a, b, c = LI()


def LI(): return list(map(int, sys.stdin.buffer.readline().split()))

# a = I()


def I(): return int(sys.stdin.buffer.readline())

# abc def
# a, b = LS()


def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()

# a = S()


def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')

# 2
# 1
# 2
# [1, 2]


def IR(n): return [I() for i in range(n)]

# 2
# 1 2 3
# 4 5 6
# [[1,2,3], [4,5,6]]


def LIR(n): return [LI() for i in range(n)]

# 2
# abc
# def
# [abc, def]


def SR(n): return [S() for i in range(n)]

# 2
# abc def
# ghi jkl
# [[abc,def], [ghi,jkl]]


def LSR(n): return [LS() for i in range(n)]

# 2
# abcd
# efgh
# [[a,b,c,d], [e,f,g,h]]


def SRL(n): return [list(S()) for i in range(n)]


def main():
    n, m = LI()
    # py = LIR(m)
    lst = [[] for i in range(n)]
    ans = [0 for i in range(m)]

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

    for i in range(n):
        if len(lst[i]) > 1:
            lst[i].sort()
        for j, pair in enumerate(lst[i]):
            ans[pair[1]] = str(i+1).zfill(6) + str(j + 1).zfill(6)

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


if __name__ == "__main__":
    main()