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())
py = [list(map(int, input().split())) for i in range(m)]
py = [[py[i][0], py[i][1], i] for i in range(m)]
py = sorted(py)
p_list = [1 for _ in range(n+1)]
result = []
for i in range(m):
    result.append([py[i][2], py[i][0], p_list[py[i][0]]])
    p_list[py[i][0]] += 1
result = sorted(result)
for a, b, c in result:
    print("{:06}{:06}".format(b, c))

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
si = []
for i in range(m):
    p,y = map(int,input().split())
    si.append([i,p,y])
si.sort(key=lambda x:x[2])
ans = []
all = [0]*n
for i in range(m):
    now = si[i]
    all[now[1]-1] += 1
    x = all[now[1]-1]
    ans.append([now[0],now[1],x])
ans.sort(key=lambda x:x[0])
for i in range(m):
    now = ans[i]
    str_1 = str(now[1])
    str_1 = str_1.zfill(6)
    str_2 = str(now[2])
    str_2 = str_2.zfill(6)
    print(str_1+str_2)

Submission status: Accepted

Solution code:
from operator import itemgetter
N, M = map(int, input().split())
# info = [tuple(map(int, input().split())) for _ in range(M)]
info = []
for i in range(M):
    P, Y = map(int, input().split())
    info.append((P, Y, i))
info.sort()
# print(info)
num = set()
ID = []
for i in range(M):
    if not info[i][0] in num:
        num.add(info[i][0])
        j = 1
    else:
        j += 1
    left = str(info[i][0])
    right = str(j)
    left = left.zfill(6)
    right = right.zfill(6)
    ID.append((left + right, info[i][2]))
    # print(ID)
ID = sorted(ID, key=lambda x: x[1])
# ID = sorted(ID, key=itemgetter())
# print(ID)
for id, index in ID:
    print(id)

Submission status: Accepted

Solution code:
import bisect

def main():
  N,M = map(int,input().split())
  pref = [[] for i in range(N)]
  id = [[]] * M
  
  for i in range(M):
    p,y = map(int,input().split())
    id[i] = [p,y]
    pref[p - 1].append(y)
    #pref[p - 1] = sorted(pref[p - 1])
  
  for i in range(N):
    pref[i] = sorted(pref[i])
  
  orders = [0] * N
  
  for i in range(M):
    p = id[i][0] - 1
    y = id[i][1]
    order = str(bisect.bisect_left(pref[p],y) + 1)
    city = str(p + 1)
    ID = ""
    ID += "0" * (6 - len(city)) + city + "0" * (6 - len(order)) + order
    print(ID)

if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
import bisect

N,M = map(int,input().split())
pref = [[] for i in range(N)]
id = [[]] * M

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

for i in range(N):
  pref[i] = sorted(pref[i])

orders = [0] * N

for i in range(M):
  p = id[i][0] - 1
  y = id[i][1]
  order = str(bisect.bisect_left(pref[p],y) + 1)
  city = str(p + 1)
  ID = ""
  ID += "0" * (6 - len(city)) + city + "0" * (6 - len(order)) + order
  print(ID)

Submission status: Accepted

Solution code:
import sys

input=sys.stdin.readline

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

data=[[] for i in range(0,N)]
ans=[0 for i in range(0,M)]
for i in range(0,M):
    data[P[i]-1].append([Y[i],i])
for i in range(0,N):
    data[i].sort()

for i in range(0,N):
    if data[i]!=[]:
        for j in range(0,len(data[i])):
            p=i+1
            x=j+1
            pp=''
            xx=''
            while 6-len(str(p))>len(pp):
                pp+='0'
            while 6-len(str(x))>len(xx):
                xx+='0'
            ans[data[i][j][1]]=pp+str(p)+xx+str(x)
for i in range(0,M):
    print(ans[i])

Submission status: Accepted

Solution code:
from collections import defaultdict

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

order = dict()
for i in range(M):
    key = input().strip()
    PYm[i] = list(map(int, key.split()))
    order[key] = i

d = defaultdict(list)
for i in range(M):
    d[PYm[i][0]].append(PYm[i][1])

res = dict()
for pi, ys in d.items():
    for i, y in enumerate(sorted(ys), 1):
        res["{} {}".format(pi, y)] = "{:0>6}{:0>6}".format(pi, i)

for key, _ in sorted(order.items(), key=lambda x: x[1]):
    print(res[key])

Submission status: Accepted

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

for i in range(len(s)):
    s[i].sort()

ans=[]
for i,ss in enumerate(s):
    for j,sss in enumerate(ss):
        id_no=''
        id_no+='0'*(6-len(str(i+1)))+str(i+1)
        id_no+='0'*(6-len(str(j+1)))+str(j+1)
        s[i][j].append(id_no)

for i,ss in enumerate(s):
    for j,sss in enumerate(ss):
        ans.append(s[i][j])
ans.sort(key=lambda x:x[1])
for aa in ans:
    print(aa[2])

Submission status: Accepted

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

for i in range(len(s)):
    s[i].sort()

ans=[]
for i,ss in enumerate(s):
    for j,sss in enumerate(ss):
        if ss:
            if sss:
                id_no=''
                id_no+='0'*(6-len(str(i+1)))+str(i+1)
                id_no+='0'*(6-len(str(j+1)))+str(j+1)
                s[i][j][2]=id_no

for i,ss in enumerate(s):
    for j,sss in enumerate(ss):
        ans.append(s[i][j])
ans.sort(key=lambda x:x[1])
for aa in ans:
    print(aa[2])

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
city = []
for i in range(m):
    x, y = map(int, input().split())
    city.append(list([x, y, i]))

city.sort()
cnt = 1

tmppref = city[0][0]

for i in range(m):
    city[i][1] = cnt
    cnt += 1
    if i < m - 1 and tmppref != city[i + 1][0]:
        cnt = 1
        tmppref = city[i+1][0]
city = sorted(city, key=lambda x: x[2])
for i in range(m):
    pref = city[i][0]
    num = city[i][1]
    ans = str(pref).zfill(6) + str(num).zfill(6)
    print(ans)

Submission status: Accepted

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

D={}
for py in PY:
    try:
        if D[py[0]]=='':
            pass
    except:
        D[py[0]]=[py[1]]
        continue
    D[py[0]].append(py[1])

for k in D.keys():
    D[k].sort()

def binary_tree(lst,key):
    left=0
    right=len(lst)-1
    while left<=right:
        mid=(left+right)//2
        if lst[mid]==key:
            return mid+1
        elif lst[mid]<key:
            left=mid+1
        else:
            right=mid-1
    return -1

for py in PY:
    l=D[py[0]]
    ans=str(py[0]).zfill(6)
    ans+=str(binary_tree(l,py[1])).zfill(6)
    print(ans)

Submission status: Accepted

Solution code:

n,m = map(int,input().split())
data = [[0,0,0] for i in range(m)]
ans = ['']*m
city = [0]*n
for i in range(m):
    data[i] = list(map(int,input().split()))+[i]
    data[i][0] -= 1
for d in sorted(data,key=lambda x:x[1]):
    city[d[0]] += 1
    ans[d[2]] = str(d[0]+1).zfill(6)+str(city[d[0]]).zfill(6)
for i in ans:
    print(i)

Submission status: Accepted

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

for v in range(m):
    l[v].append(v)

l = sorted(l)


x = l[0][0]
y = 1

for i in range(m):
    if l[i][0] == x:
        l[i][1] = y
        y += 1
    else:
        y = 1
        l[i][1] = y
        y += 1
        x = l[i][0]

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

z = []
for j in range(m):
    z.append(str(l[j][0]).rjust(6,'0') + str(l[j][1]).rjust(6,'0'))

for k in range(m):
    print(z[k])

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
l = [list(map(int, input().split(' '))) for _ in range(m)]
#print(l)
for v in range(m):
    l[v].append(v)

l = sorted(l)
#print(n,m)
#print(l)

x = l[0][0]
y = 1

for i in range(m):
    if l[i][0] == x:
        l[i][1] = y
        y += 1
    else:
        y = 1
        l[i][1] = y
        y += 1
        x = l[i][0]
#print(l)
l = sorted(l, key=lambda x:(x[2]))
#print(l)
z = []
for j in range(m):
    z.append(str(l[j][0]).rjust(6,'0') + str(l[j][1]).rjust(6,'0'))
#z.sort()
for k in range(m):
    print(z[k])

Submission status: Accepted

Solution code:
n, m = map(int,input().split())
PY = []
for _ in range(m):
    PY.append(list(map(int,input().split())))
sortedPY = sorted(PY, key=lambda x: x[1])

d = {}
o = [1]*(n+1)
for i in sortedPY:
    d[(i[0],i[1])] = o[i[0]]
    o[i[0]] += 1

for i in PY:
    print(str(i[0]).zfill(6) + str(d[(i[0],i[1])]).zfill(6))

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
ls = [[] for _ in range(N)]
for i in range(M):
    p, y = map(int,input().split())
    ls[p-1].append((y, i))
ids = [None]*M
for i in range(N):
    ls[i].sort()
    for j in range(len(ls[i])):
        y,k = ls[i][j]
        ids[k] = "{:0>6}{:0>6}".format(i+1,j+1)
print(*ids, sep="\n")

Submission status: Accepted

Solution code:

if __name__ == '__main__':
    N,M=list(map(int,input().split()))
    P={i:[] for i in range(N)}
    Cities={i:[] for i in range(M)}
    for i in range(M):
        p,y=list(map(int, input().split()))
        P[p-1].append((i,y))
    for i,p in P.items():
        p.sort(key=lambda x:x[1])
        for id in range(len(p)):
            number=p[id][0]
            temp='{}'.format(i+1).zfill(6)
            temp+='{}'.format(id+1).zfill(6)
            Cities[number]=temp

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

Submission status: Accepted

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

Ans=[]
tmp=1
for j in range(M-1):
    p,y,i=PY[j]
    Ans.append(('0'*(6-len(str(p)))+str(p)+'0'*(6-len(str(tmp)))+str(tmp),i))
    if PY[j][0]==PY[j+1][0]:
        tmp+=1
    else:
        tmp=1
p,y,i=PY[M-1]
Ans.append(('0'*(6-len(str(p)))+str(p)+'0'*(6-len(str(tmp)))+str(tmp),i))
        
Ans=sorted(Ans,key=lambda x:x[1])
for i in range(M):
    print(Ans[i][0])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

n,m=mii()
arr=[]
for i in range(m):
    a,b=mii()
    arr.append([a,b,i])

arr.sort(key=lambda x:(x[0],x[1]))
ans=[]
cnt=1
for i in range(m):

    c= str(arr[i][0]).zfill(6)+str(cnt).zfill(6)
    ans.append([c,arr[i][2]])
    if i+1<m:
        if arr[i][0]==arr[i+1][0]:
            cnt+=1
        else:
            cnt=1

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

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
P = [0] * M
Y = [0] * M

data = [[] for _ in range(N + 1)]

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

for k in set(P):
    data[k].sort()

x = [{} for _ in range(N + 1)]

for k in set(P):
    c = 0
    for v in data[k]:
        c += 1
        x[k][v] = c

for i in range(M):
    id_number = "{:06}{:06}".format(P[i], x[P[i]][Y[i]])
    print(id_number)

Submission status: Accepted

Solution code:
from operator import itemgetter
n,m=map(int,input().split())
data=[]
for i in range(m):
    p_i,y_i=map(int,input().split())
    data.append([p_i,y_i,i])
data.sort()
data.append([n+1,0,m])
buf=1
for i in range(m):
    data[i].append(buf)
    if data[i][0]==data[i+1][0]:
        buf+=1
    else:
        buf=1
data.sort(key=itemgetter(2))
for i in range(m):
    ans_p=data[i][0]
    ans_y=data[i][3]
    ans_p=(str(ans_p)).zfill(6)
    ans_y=(str(ans_y)).zfill(6)
    print(ans_p+ans_y)

Submission status: Accepted

Solution code:
import sys

def read():
    return sys.stdin.readline().rstrip()

def main():
    n, m = map(int, read().split())
    cities = sorted([[int(j) for j in read().split()] + [i] for i in range(m)])
    p, x = 0, 1
    a = [(0, "") for _ in range(m)]
    for i, c in enumerate(cities):
        if c[0] == p:
            x += 1
        else:
            p = c[0]
            x = 1
        a[i] = (c[2], "{:0>6}{:0>6}".format(p, x))
    for _, ai in sorted(a):
        print(ai)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from operator import itemgetter
n,m=map(int,input().split())
T=[list(map(int,input().split())) for i in range(m)]
for i in range(m):
  T[i].append(i)
T.sort(key=itemgetter(0,1))

cnt=1
ans=[[] for _ in range(m)]
for i in range(m-1):
  ans[T[i][2]]=str(T[i][0]).zfill(6)+str(cnt).zfill(6)
  if T[i][0]==T[i+1][0]:
    cnt+=1
  else:
    cnt=1
ans[T[m-1][2]]=str(T[m-1][0]).zfill(6)+str(cnt).zfill(6)
print(*ans,sep='\n')

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(20000000)
S = input().split(" ")
n = int(S[0])
m = int(S[1])

py = []

for i in range(m):
    py.append([int(s) for s in input().split(" ")])

def prepare(n, data):
    result = [0 for i in range(n)]
    dict = {}
    data = sorted(data,key=lambda x:x[1])
    for d in data:
        i = d[0] - 1
        result[i] = result[i] + 1
        dict.__setitem__(generateID(d[0], d[1]), str(d[0]).zfill(6) + str(result[i]).zfill(6))

    return dict


def generateID(start, to):
    if start < to:
        start, to = to, start

    return start * 100000 + to

dict = prepare(n, py)

for p in py:
    print(dict[generateID(p[0],p[1])])

Submission status: Accepted

Solution code:
from collections import defaultdict 
n,m = map(int,input().split())
py = []
for i in range(m):
    p,y = map(int,input().split())
    py.append([p,y])
spy = sorted(py,key=lambda x:x[1])

cnt = [0]*n
id =  defaultdict(int)
for i in spy:
    p,y = i
    cnt[p-1] += 1
    id[(p,y)] = str(p).zfill(6)+str(cnt[p-1]).zfill(6)

for i in py:
    p,y = i
    print(id[(p,y)])

Submission status: Accepted

Solution code:
import sys
import math
import fractions
import bisect
import queue
import heapq
import collections
import itertools
sys.setrecursionlimit(4100000)

MOD = int(1e9+7)
PI = 3.14159265358979323846264338327950288
INF = 1e18

'''
1行のint=====================================
N, K = map(int, input().split())
N, M = map(int, input().split())
A, B = map(int, input().split())

H, W = map(int, input().split())

L, R = map(int, input().split())

1行のstring=================================
S, T = input().split()

1行の整数配列================================
P = list(map(int,input().split()))

A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
D = list(map(int,input().split()))

L = list(map(int,input().split()))
R = list(map(int,input().split()))

T = list(map(int,input().split()))

改行あり整数==================================
X = []
Y = []
for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    X.append(x1)
    Y.append(y1)

A = []
for i in range(N):
    a=int(input())
    A.append(a)

Pair = []
for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    Pair.append((x1, y1))
    
2次元整数配列=====================================
A = []
for i in range(N):
    tmp = list(map(int,input().split()))
    A.append(tmp)


N行M列の初期化====================================
dp = [[VAL] * RETU for i in range(GYO)]

'''



N, M = map(int, input().split())
PYn = []

for i in range(M):
    x1,y1=[int(i) for i in input().split()]
    PYn.append((x1, y1, i))

PYn.sort()

past = [1]*(N+1)
ans = [0]*M # p*1000000+n
for pyn in PYn:

    ans[pyn[2]] = pyn[0]*1000000 + past[pyn[0]]
    past[pyn[0]] += 1


final = []
for a in ans:
    final.append(str(a).zfill(12))

for f in final:
    print(f)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
PY = [list(map(int, input().split())) for _ in range(m)]
SortedPY = sorted(PY, key=lambda x: x[1])

from collections import defaultdict
d = defaultdict(int)
memo = [1]*(n+1)
for py in SortedPY:
    p, y = py
    d[(p, y)] = memo[p]
    memo[p] += 1

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

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()

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

    sorted_PY  = sorted(PY)

    ans = [{} for _ in range(N+1)]
    i = 0
    pre = sorted_PY[0][0]
    for p, y in sorted_PY:
        if pre != p:
            i = 0
        i += 1
        ans[p][y] = i
        pre = p

    for p, y in PY:
        print(str(p).zfill(6) + str(ans[p][y]).zfill(6))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from operator import itemgetter

read = sys.stdin.read

N, M, *PY = map(int, read().split())
P = PY[::2]
Y = PY[1::2]

P, Y, I = zip(*sorted(zip(P, Y, range(M)), key=itemgetter(0, 1)))
P = list(map(str, P))
answer = []
prev_p = ''
n = 0
for p, i in zip(P, I):
    if prev_p == p:
        n += 1
    else:
        prev_p = p
        n = 1
    answer.append((p.zfill(6) + str(n).zfill(6), i))

answer.sort(key=itemgetter(1))
answer = [i for i, _ in answer]
print('\n'.join(answer))

Submission status: Accepted

Solution code:
def compress(arr):
    *XS, = set(arr)
    XS.sort()
    return {e: i+1 for i, e in enumerate(XS)} 
n,m=map(int,input().split())
s=[[] for i in range(n+1)]
p=[0]*m
y=[0]*m
for i in range(m):
    p[i],y[i]=map(int,input().split())
    s[p[i]].append(y[i])
for i in range(1,n+1):
    s[i]=compress(s[i])
for i in range(m):
    print("0"*(6-len(str(p[i]))),p[i],"0"*(6-len(str(s[p[i]][y[i]]))),s[p[i]][y[i]],sep="")

Submission status: Accepted

Solution code:
f = lambda:map(int,input().split())
n,m = f()
ll = [list(f()) for _ in range(m)]
l = [0]*n
d = {}
for p,y in sorted(ll,key=lambda k:k[1]):
  l[p-1] += 1
  d[y] = str(p).zfill(6)+str(l[p-1]).zfill(6)
for l in ll:
  print(d[l[1]])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
f = lambda:map(int,input().split())
n,m = f()
ll = [list(f()) for _ in range(m)]
l = [0]*n
d = {}
for p,y in sorted(ll,key=lambda k:k[1]):
  l[p-1] += 1
  d[y] = str(p).zfill(6)+str(l[p-1]).zfill(6)
for l in ll:
  print(d[l[1]])

Submission status: Accepted

Solution code:
import copy

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

cnt = [0]*(10**5+4)

yy = []
yp = []
for _ in range(m):
    a,b = map(int,input().split())
    a,b = b,a
    yy.append([a,0])
    yp.append([a,b])

inlist = copy.deepcopy(yp)
yp.sort()
yy = dict(yy)

for i in range(m):
    cnt[yp[i][1]]+=1
    yy[yp[i][0]] = cnt[yp[i][1]]

for key,value in inlist:
    print("{:06}{:06}".format(value,yy[key]))

Submission status: Accepted

Solution code:
n,m = [int(x) for x in input().split()]
py = []
for i in range(m):
    p,y = [int(x) for x in input().split()]
    py.append([p,y,i+1])

def zero(num):
    return str(num).zfill(6)


if m == 1:
    print(zero(py[0][0])+zero(1))
else:
    year_py = sorted(py, key=lambda x: x[1])
    dic = {str(x): 0 for x in range(1,n+1)}

    for i in range(m):
        dic[str(year_py[i][0])] += 1
        year_py[i].append(dic[str(year_py[i][0])])
    yb_py = sorted(year_py, key=lambda x: x[2])

    for i in range(m):
        print(zero(yb_py[i][0]) + zero(yb_py[i][3]))

Submission status: Accepted

Solution code:
def zeroPadding(num):
    return "%06d"%num

def zeroPadding10(num):
    return "%010d"%num

class Row:
    def __init__(self, i, pref_id, year):
        self.i = i
        self.pref_id = pref_id
        self.year = year
        self.city_id = -1
        
    def __str__(self):
        return "{i: %d, pref_id: %d, year: %d, city_id: %d}"%(self.i, self.pref_id, self.year, self.city_id)
        
    def set_city_id(self, city_id):
        self.city_id = city_id
            
    def get_sort_key(self):
        return zeroPadding(self.pref_id ) + zeroPadding10(self.year) 
            
    def get_str(self):
        return zeroPadding(self.pref_id ) + zeroPadding(self.city_id)

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

row_list = []

for i in range(M):
    d = list(map(int,input().split())) 
    row_list.append(Row(i, d[0], d[1]))

row_list = sorted(row_list, key=lambda x: x.get_sort_key())

now_pref_id = -1
cnt = 1

result = []
for i, row in enumerate(row_list):
    if row.pref_id != now_pref_id:
        now_pref_id = row.pref_id
        cnt = 1
    
    row.set_city_id(cnt)
    row_list[i] = row
    cnt += 1

[print(x.get_str()) for x in sorted(row_list, key=lambda x: x.i)]

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
p=[]
q={}
for i in range(m):
    pi,yi=map(int,input().split())
    p.append([pi,yi])
p2=sorted(p,key=lambda x:x[1])
#print(p)
    
xs=[0]*(n+1)
for i in p2:
    pi,yi=i
    xs[pi]=xs[pi]+1
    q[yi]=xs[pi]

for i in p:
    pi,yi=i
    spi=str(pi).rjust(6,"0")    
    sxi=str(q[yi]).rjust(6,"0")    
    print(spi+sxi)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
f = lambda:map(int,input().split())
n,m = f()
llm = []
lln = [[] for _ in range(n)]
ll = []
for i in range(m):
  p,y = f()
  llm.append([i,p,y])
  lln[p-1].append([y,i])
for j in range(n):
  lln[j].sort()
  for k in range(len(lln[j])):
    ll.append([lln[j][k][1],j+1,k+1])
ll.sort()
for i in range(m):
  print(str(ll[i][1]).zfill(6)+str(ll[i][2]).zfill(6))

Submission status: Accepted

Solution code:
import sys
import bisect
read = sys.stdin.read
readline = sys.stdin.readline

def main2():
    N,M,*PY = map(int, read().split())
    PY_input = []
    PY_dict = {}
    for p, y in zip(*[iter(PY)]*2):
        PY_input.append((p, y))
        PY_dict.setdefault(p, []).append(y)

    for i in PY_dict.values():
        i.sort()

    for p, y in PY_input:
        print("{:06}{:06}".format(p, bisect.bisect_right(PY_dict[p], y)))


if __name__ == "__main__":
    main2()

Submission status: Accepted

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

def main():
    N,M = map(int, input().split())
    PY_input = []
    PY_dict = {}
    for _ in range(M):
        p, y = map(int, input().split())
        PY_input.append((p, y))
        PY_dict.setdefault(p, []).append(y)

    for i in PY_dict.values():
        i.sort()

    for p, y in PY_input:
        print("{:06}{:06}".format(p, bisect.bisect_right(PY_dict[p], y)))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from operator import itemgetter
def input():
    return sys.stdin.readline()
N, M = map(int, input().split())
chk = {i+1: 1 for i in range(N)}
PY = sorted([list(map(int, input().split())) + [i+1] for i in range(M)], key=itemgetter(0,1))
ans = []
for i in range(M):
    idx = PY[i][0]
    ans.append(('{:0>6}{:0>6}'.format(idx, chk[idx]), PY[i][2]))
    chk[idx] += 1
ans.sort(key=itemgetter(1))
for k, v in ans:
    print(k)

Submission status: Accepted

Solution code:
N,M = map(int, input().split())
PY=[]
for i in range(M):
    _list=list(map(int, input().split()))
    _list.append(i)
    PY.append(_list)
    #PY.extend([list(map(int, input().split()))])
    ##PY = [list(map(int, input().split())) for _ in range(M)]
PY.sort(key=lambda x: (x[0], x[1]))
#print(PY)
cnt=0
for i in range(M):
    if i==0:
        cnt=1
        forward = (6-len(str(PY[i][0])))*'0'+str(PY[i][0])
        backward = (6-len(str(cnt)))*'0'+str(cnt)
        PY[i].append(forward+backward)
        #print(forward+backward)
    else:
        if PY[i][0]==PY[i-1][0]:
            cnt+=1
            forward = (6-len(str(PY[i][0])))*'0'+str(PY[i][0])
            backward = (6-len(str(cnt)))*'0'+str(cnt)
            PY[i].append(forward+backward)
            #print(forward+backward)
        else:
            cnt=1
            forward = (6-len(str(PY[i][0])))*'0'+str(PY[i][0])
            backward = (6-len(str(cnt)))*'0'+str(cnt)
            PY[i].append(forward+backward)
            #print(forward+backward)
#print(PY)
PY.sort(key=lambda x: x[2])
for i in range(M):
    print(PY[i][3])

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, 0])

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

# print(a)

count_l1 = a[0][0]
index = 0
for i in range(m):
    if i == 0:
        a[0][3] = 1
        index = 1
    else:
        if count_l1 == a[i][0]:
            index += 1
            a[i][3] = index
        else:
            index = 1
            count_l1 = a[i][0]
            a[i][3] = index
    # print(a[i])

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

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

Submission status: Accepted

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

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

arr[0][1] = 1
P_cnt = [1 for _ in range(10 ** 6)]
ans_list = [0] * M
for p, y, i in arr:
    ans_list[i] = [str(p).zfill(6) + str(P_cnt[p]).zfill(6), i]
    P_cnt[p] += 1

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

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()

P = [0]*(N+1)
ID = []

for p,y,i in py:
    
    P[p] += 1 ##どの県に何個市があるかカウント

    p_tmp = str(p)
    y_tmp = str(P[p])

    upper = "0"*max(0,6-len(p_tmp))+p_tmp
    lower = "0"*max(0,6-len(y_tmp))+y_tmp

    ID.append([i,upper+lower])

ID.sort()

for _,i in ID:
    print(i)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc113/tasks/abc113_c
# 入力が10**5とかになったときに100ms程度早い
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


N, M = read_ints()
data = []
for i in range(M):
    data.append(list(map(int, read().split())) + [i])

data.sort()
ans = []
cnt = [0] * (N + 1)  # それぞれの出現回数をカウントする →x番目を取得するため
for p, y, i in data:
    cnt[p] += 1
    x = cnt[p]
    ans.append((i, str(p).zfill(6) + str(x).zfill(6)))

ans.sort()
for _, a in ans:
    print(a)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
D = []#D[i] = [i_i,p_i,y_i]

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

S =[None for i in range(M)]

p_ = D[0][1]
n = 0

for i in range(len(D)):
  if p_ != D[i][1]:
    p_ = D[i][1]
    n = 1
  else:
    n+=1
  S[D[i][0]] =str(D[i][1]).zfill(6)+str(n).zfill(6)


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

Submission status: Accepted

Solution code:
def main():
    N, M = map(int, input().split())
    d = {}
    l = []
    for i in range(M):
        p, y = map(int, input().split())
        if p in d:
            d[p].append((y, i))
        else:
            d[p] = [(y, i)]
        l.append((p, y))
    d2 = {}
    for i in d:
        t = d[i]
        t.sort(key= lambda x: x[0])
        for y, v in enumerate(t, start=1):
            d2[(i, v[0])] = y
    for i in l:
        print(str(i[0]).zfill(6) + str(d2[i]).zfill(6))
main()

Submission status: Accepted

Solution code:
from operator import itemgetter
def main():
    N,M = map(int,input().split())
    py = [list(map(int,input().split())) for _ in range(M)]
    [py[i].append(i) for i in range(M)]
    py = sorted(py,key=itemgetter(1))
    py = sorted(py,key=itemgetter(0))
    now = 0
    num = 1
    ans = []
    for i in range(M):
        if now != py[i][0]:
            now = py[i][0]
            num = 1
        else:
            num += 1
        tmp = str(now).zfill(6)+str(num).zfill(6)
        ans.append([tmp,py[i][2]])
    ans = sorted(ans,key=itemgetter(1))
    for i in range(M):
        print(ans[i][0])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def SixDigit(x):
    while len(x) < 6:
        x = '0' + x
    return x
        
n, m = map(int, input().split())
l = []
for i in range(m):
    p, y = map(int, input().split())
    l.append([p, y, i])
l.sort()

count = 1
ans = [[l[0][2], l[0][0], count]]
for j in range(1, m):
    if l[j][0] == l[j-1][0]:
        count += 1
        ans.append([l[j][2], l[j][0], count])
    elif l[j][0] != l[j-1][0]:
        count = 1
        ans.append([l[j][2], l[j][0], count])
    
ans.sort()
for k in range(m):
    print(SixDigit(str(ans[k][1]))+SixDigit(str(ans[k][2])))

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
N,M=map(int,input().split())
l=[None]*M
for i in range(M):
    P,Y=map(int,input().split())
    l[i]=(P,Y,i)
l.sort()
a=[None]*M
s=0
t=1
for i in l:
    if i[0]==s:
        t+=1
    else:
        t=1
        s=i[0]
    a[i[2]]="{:06d}".format(i[0]) + "{:06d}".format(t)
print(*a,sep="\n")