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:
import sys
import math  # noqa
import bisect  # noqa
import queue  # noqa


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


if __name__ == '__main__':
    N, M = map(int, input().split())
    PY = []
    for i in range(M):
        P, Y = map(int, input().split())
        PY.append([Y, P, i + 1])
    PY.sort()

    # cnt: key=県, value=すでに幾つの市がその県に属しているか
    # res: [市の番号, 県の番号, 順番]
    cnt = {}
    res = []
    for y, p, i in PY:
        if p not in cnt:
            cnt[p] = 1
        else:
            cnt[p] += 1
        res.append([i, p, cnt[p]])

    res.sort()
    for i, p, x in res:
        print('{:06}{:06}'.format(p, x))

Submission status: Accepted

Solution code:
import math  # noqa
import bisect  # noqa
import queue  # noqa


if __name__ == '__main__':
    N, M = map(int, input().split())
    PY = []
    for i in range(M):
        P, Y = map(int, input().split())
        PY.append([Y, P, i + 1])
    PY.sort()

    # cnt: key=県, value=すでに幾つの市がその県に属しているか
    # res: [市の番号, 県の番号, 順番]
    cnt = {}
    res = []
    for y, p, i in PY:
        if p not in cnt:
            cnt[p] = 1
        else:
            cnt[p] += 1
        res.append([i, p, cnt[p]])

    res.sort()
    for i, p, x in res:
        print('{:06}{:06}'.format(p, x))

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007

#A
def A():
    return

#B
def B():
    return

#C
def C():
    n, m = LI()
    py = LIR(m)
    pya = py[::1]
    py.sort(key=lambda x: x[1])
    city = [1 for i in range(n)]
    dicity = {}
    for p, y in py:
        dicity[(p,y)] = city[p-1]
        city[p-1] += 1    
    for p, y in pya:
        a = "00000" + str(p)
        a = a[-6:]
        b = "00000" + str(dicity[(p, y)])
        b = b[-6:]
        print(a+b)

    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    C()

Submission status: Accepted

Solution code:
# int(input()) # 入力が1つ
n, m = map(int, input().split()) # 入力が複数
# [int(i) for i in input().split()] # 配列で数字

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

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

ans = [0] * m
for i in range(n):
    cities = prefec[i]
    cities.sort(key=lambda x: x[0])
    for j in range(len(cities)):
        _, index = cities[j]
        p = i + 1
        num = j + 1
        ans[index] = '0' * (6 - len(str(p))) + str(p) + '0' * (6 - len(str(num))) + str(num)

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

Submission status: Accepted

Solution code:
from collections import Counter
N, M = list(map(int,input().split()))
city_list = [list(map(int,input().split())) +[i+1]  for i in range(M)]
city_list_sorted = sorted(city_list,key=lambda x: (x[0],x[1]) )
pre = 0
counter = 0

for i in range(M):
  if pre == city_list_sorted[i][0]:
    counter+=1
    city_list_sorted[i][1] = counter
  else:
    counter = 1
    city_list_sorted[i][1] = counter
    pre = city_list_sorted[i][0]

anslist = [[x[2]]+[format(x[0],'0>6') + format(x[1],'0>6') ] for x in city_list_sorted]
[print(x[1]) for x in sorted(anslist)]

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
ken = [[] for i in range(n)]
jun = [0] * m
p = [0] * m
for i in range(m):
    p[i],y = map(int,input().split())
    ken[p[i]-1].append((y,i))
    
for i in range(n):
    if ken[i] == []:
        continue
    else:
        ken[i].sort()
        for j in range(len(ken[i])):
            jun[ken[i][j][1]] = j+1
            
for i in range(m):
    jun[i] += p[i] * 1000000
    ss = str(jun[i])
    s = "0"*(12-len(ss)) + ss
    print(s)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
pref_ls = [[0] for _ in range(n+1)]
keys_ls = [0] * m
for i in range(m):
    p, y = map(int,input().split())
    pref_ls[p].append(y)
    keys_ls[i] = [p,y]
for i in range(n+1):
    pref_ls[i].sort()

# 含まれてるならそのインデックス 、含まれてないなら-1を返す
def binary_search(l, item):
    left = 0
    right = len(l) - 1
    while left <= right:
        mid  = (left + right) // 2
        if l[mid] == item:
            return mid
        elif l[mid] < item:
            left = mid + 1
        else:
            right = mid - 1
    return -1
for i in range(m):
    p,y = keys_ls[i]
    rank = binary_search(pref_ls[p], y)
    ans = str(p).zfill(6) + str(rank).zfill(6)
    print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
pyi=[[] for i in range(n)]
for i in range(m):
    p,y=map(int,input().split())
    pyi[p-1].append([y,i])
ans=[]
for i in range(n):
    pyi[i].sort()
    for j in range(len(pyi[i])):
        ans.append([(6-len(str(i+1)))*"0"+str(i+1)+(6-len(str(j+1)))*"0"+str(j+1),pyi[i][j][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())
C=[]
for i in range(m):
    p,y=map(int,input().split())
    C.append([p,y,i])
C.sort()
A=[""]*m
nowP=0
nowX=0
for c in C:
    p=c[0]
    y=c[1]
    i=c[2]
    if p==nowP:
        nowX+=1
        lenX=len(str(nowX))
        A[i]="0"*(6-lenP)+str(nowP)+"0"*(6-lenX)+str(nowX)
    else:
        nowP=p
        lenP=len(str(nowP))
        nowX=1
        lenX=1
        A[i]="0"*(6-lenP)+str(nowP)+"0"*(6-lenX)+str(nowX)
print(*A,sep="\n")

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
py = []
p_y = [[] for i in range(n)]
for _ in range(m):
    p,y = map(int,input().split())
    py.append((p,y))
    p_y[p-1].append(y)
ans = {}
for i, tmp in enumerate(p_y):
    cnt = 1
    p_y[i] = tmp.sort()
    for j, jj in enumerate(tmp):

        ans[(i+1, jj)] = str(i+1).zfill(6) + str(j+1).zfill(6)


for i, tmp in enumerate(py):
    print(ans[tmp])

Submission status: Accepted

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

A = []
for i in range(M):
  A.append([i,1000000000000])

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

PY.sort()

P = 0


for i in range(M):
  if P != PY[i][0]:
    P = PY[i][0]
    S = 1

  else:
    S += 1

  PY[i][3] += PY[i][0]*1000000+S
#print(PY)
PY.sort(key=lambda x: x[2])

for i in range(M):
  ans = str(PY[i][3])
  print(ans[1:])

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[0],x[1]))
cnt = 1
ans = [""]*m
for i in range(m-1):
  ans[py[i][2]] = "0"*(6-len(str(py[i][0])))+str(py[i][0]) + "0"*(6-len(str(cnt)))+str(cnt)
  if py[i][0] == py[i+1][0]:
    cnt += 1
  else:
    cnt = 1
ans[py[m-1][2]]="0"*(6-len(str(py[m-1][0])))+str(py[m-1][0]) + "0"*(6-len(str(cnt)))+str(cnt)
for i in range(m):
  print(ans[i])

Submission status: Accepted

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

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

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

p = cities[0][0]
cnt = 1
for i in range(M):

    if (cities[i][0] == p):
        cities[i].append(str(p).zfill(6) + str(cnt).zfill(6))
        cnt += 1
    else:
        p = cities[i][0]
        cnt = 1
        cities[i].append(str(p).zfill(6) + str(cnt).zfill(6))
        cnt += 1

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

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

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
pref = [[] for _ in range(N)]
P,Y = [0]*M,[0]*M
for i in range(M):
    P[i],Y[i] = map(int, input().split())
    pref[P[i]-1].append(Y[i])

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

from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort

def solve(P,Y,pref):
    ans = []
    for p, y in zip(P,Y):
        ind = bisect_left(pref[p-1],y)+1
        num = '0'*(6-len(str(p)))+str(p)+'0'*(6-len(str(ind)))+str(ind)
        ans.append(num)
    return ans
print(*solve(P,Y,pref),sep='\n')

Submission status: Accepted

Solution code:
from collections import defaultdict
n, m = map(int, input().split())
l = []
dic = defaultdict(list)
for i in range(m):
    p, y = map(int, input().split())
    dic[p].append(y)
    l.append([p, y])
for key, value in dic.items():
    dic[key] = {num: index+1 for index,num in enumerate(sorted(value))}
for p, y in l:
    print(str(p).zfill(6)+str(dic[p][y]).zfill(6))

Submission status: Accepted

Solution code:
def I(): return map(int, input().split())
n, m = I()
d = []
for _ in range(m):
    d += [list(I())]
u = sorted([[i, j] for i, j in enumerate(d)], key=lambda x: x[1])

f = 0
r = 0 # roop
for _, j in u:
    p, _ = j
    if f != p:
        x = 1
    u[r][1] = [str(p).zfill(6) + str(x).zfill(6)]
    x += 1
    f = p
    r += 1

for _, k in sorted(u):
    print(*k)

Submission status: Accepted

Solution code:
from collections import defaultdict


def create_id(p, o):
    return str(p).zfill(6) + str(o).zfill(6)


n, m = [int(i) for i in input().split()]
db = defaultdict(list)
for i in range(m):
    p, y = [int(i) for i in input().split()]
    db[p].append((y, i))

ans = [None] * m
for p in db:
    db[p].sort()
    for i in range(len(db[p])):
        ans[db[p][i][1]] = create_id(p, i + 1)
print(*ans, sep="\n")

Submission status: Accepted

Solution code:

from bisect import bisect_right
import sys

readline = sys.stdin.readline
n, m = map(int, readline().split())
ken = [list() for _ in range(n)]
PY = []
for _ in range(m):
    p, y = map(int, readline().split())
    PY.append((p, y))
    ken[p-1].append(y)
for i in range(n):
    ken[i].sort()

for p, y in PY:
    print(str(p).zfill(6) + str(bisect_right(ken[p-1],y)).zfill(6))

Submission status: Accepted

Solution code:
import sys

def fill(s): return '0' * (6 - len(s)) + s
def create_id(p, o): return fill(str(p)) + fill(str(o))

n, m, *py = map(int, sys.stdin.read().split())
pyi = sorted(zip(*[iter(py)] * 2 + [range(m)]))

def main():
    res = [None] * m
    prev = j = None
    for p, y, i in pyi:
        j = j + 1 if p == prev else 1
        res[i] = create_id(p, j)
        prev = p
    print(*res, sep='\n')
    
if __name__ ==  '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

def fill(s):
    while len(s) < 6: s = '0' + s
    return s

def create_id(p, o):
    return fill(str(p)) + fill(str(o))

n, m, *py = map(int, sys.stdin.read().split())
py = zip(*[iter(py)] * 2)

def main():
    db = defaultdict(list)
    i = 0
    for p, y in py:
        db[p].append((y, i))
        i += 1

    res = [None] * m
    for p in db:
        db[p].sort()
        for i in range(len(db[p])):
            res[db[p][i][1]] = create_id(p, i + 1)
    print(*res, sep='\n')

if __name__ ==  '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

def create_id(p, o):
    p = str(p)
    o = str(o)
    p = '0' * (6 - len(p)) + p
    o = '0' * (6 - len(o)) + o
    return p + o

n, m, *py = map(int, sys.stdin.read().split())
py = zip(*[iter(py)] * 2)

def main():
    db = defaultdict(list)
    i = 0
    for p, y in py:
        db[p].append((y, i))
        i += 1

    res = [None] * m
    for p in db:
        db[p].sort()
        for i in range(len(db[p])):
            res[db[p][i][1]] = create_id(p, i + 1)
    print(*res, sep='\n')

if __name__ ==  '__main__':
    main()

Submission status: Accepted

Solution code:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list
#from itertools import combinations # (string,3) 3回

mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    import collections
    import bisect
    n,m = readInts()
    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]
    #print(a)
    for x,y in p:
        z = bisect.bisect_right(a[x],y)
        print("%06d%06d"%(x,z))



if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
a,b = map(int,input().split())
py = sorted([list(map(int,input().split()))+[i] for i in range(b)])
c = 1
ans1 = [['0'*(6 - len(str(py[0][0])))+str(py[0][0])+'000001',py[0][2]]]
for i in range(1,b):
  ans = '0'*(6 - len(str(py[i][0])))
  ans += str(py[i][0])
  if py[i-1][0] == py[i][0]:
    c += 1
  else:
    c = 1
  ans += '0'*(6 - len(str(c)))
  ans += str(c)
  ans1.append([ans,py[i][2]])
ans1 = sorted(ans1,key=lambda x:x[1])
for i in ans1:
  print(i[0])

Submission status: Accepted

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

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


ans = []
last_p = -1
index = 1
for i in range(m):
  p,y,j = array[i]
  
  if p != last_p:
    index = 1
    
  number = str(p).zfill(6) + str(index).zfill(6)
  ans.append((j,number))
  
  last_p = p
  index += 1
  
for t in sorted(ans):
  print(t[1])

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
import bisect

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

pref = [[] for _ in range(N)]

res = []

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

for ar in pref:
    ar.sort()

for pre, year in res:
    p = str(pre + 1)
    p_zero = p.zfill(6)
    y = str(bisect.bisect_left(pref[pre], year) + 1)
    y_zero = y.zfill(6)
    print(p_zero + y_zero)

Submission status: Accepted

Solution code:
from collections import defaultdict

N, M = map(int, input().split())
P, Y = [], []
ylist = defaultdict(list)
pset = set()
for i in range(M):
    p, y = map(int, input().split())
    P.append(p)
    Y.append(y)
    ylist[p].append(y)
    pset.add(p)

cdict = defaultdict(dict)
for p in pset:
    syear = sorted(ylist[p])
    for i, y in enumerate(syear):
        cdict[p][y] = i + 1

for i in range(M):
    p = P[i]
    y = Y[i]
    rank = cdict[p][y]
    print('{:06}{:06}'.format(p, rank))

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
shi=[[] for i in range(N+1)]
py=[]
for i in range(M):
    p,y=map(int,input().split())
    shi[p].append(y)
    py.append([p,y])
for i in range(N+1):
    shi[i].sort()
shidic=[{} for i in range(N+1)]
for i in range(N+1):
    for j in range(len(shi[i])):
        shidic[i][shi[i][j]]=j+1
for P,Y in py:
    print(str(P).zfill(6)+str(shidic[P][Y]).zfill(6))

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
a = [[] for _ in range(n)]
for i in range(1,m+1):
  pi,yi = map(int,input().split())
  a[pi-1].append((yi,i))
ans = [0 for _ in range(m)]
for i in range(n):
  if a[i]:
    a[i].sort(key=lambda x:x[0])
    c = (i+1)*10**6
    for j in range(len(a[i])):
      ans[a[i][j][1]-1] = c + j+1
for xx in ans:
  xs = str(xx)
  xs = "0"*(12-len(xs)) + xs
  print(xs)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
dic = {}
ans = [0]*m
for i in range(m):
  p, y = map(int, input().split())
  dic.setdefault(p, []).append([y, i])
for i, j in dic.items():
  j = sorted(j)
  for k, l in enumerate(j):
    ans[l[1]]= str(i).zfill(6) + str(k + 1).zfill(6)
for i in range(len(ans)):
  print(ans[i])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]
import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

def main():
    N, M = mi()
    l = dp2(0, 3, M)
    for i in range(M):
        p, x = mi()
        l[i][0], l[i][1], l[i][2] = p, x, i 
    l.sort(key=lambda x :(x[0], x[1]))

    ans = ['' for _ in range(M)]
    cnt = 0
    bf = 1
    for i in range(M):
        a = l[i][0]
        if a > bf:
            cnt = i
        b, c = str(i+1-cnt), l[i][2]
        ans[c] = str(a).zfill(6) + b.zfill(6)
        bf = a

    
    for a in ans:
        print(a)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]
import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

def ume(x):
    x = str(x)
    if len(x) < 6:
        return '0'*(6-len(x)) + x
    return x

def main():
    N, M = mi()
    '''
    l = dp2(0, 3, M)
    cnt = [0]*(N+1)
    ans = dp2(0, 2, M)
    for i in range(M):
        p, y = mi()
        l[i][0], l[i][1], l[i][2] = p-1, y, i
        cnt[p] += 1
    for i in range(N):
        cnt[i+1] += cnt[i]

    l.sort(key=lambda x: x[0])
    for i in range(N):
        ichibu = l[cnt[i]:cnt[i+1]]
        ichibu.sort(key=lambda x: x[1])
        for j in range(cnt[i+1]-cnt[i]):
            ans[ichibu[j][2]][0] = ichibu[j][0]+1
            ans[ichibu[j][2]][1] = j+1
    
    for x, y in ans:
        print(ume(x)+ume(y))
    '''

    l = li2(M)
    pos = [[] for _ in range(N+1)]
    ans = dp2(0, 2, M)

    for a, b in l:
        pos[a].append(b)
    for a in pos:
        a.sort()
    for i, a in enumerate(l):
        ind = bisect.bisect_left(pos[a[0]], a[1])
        l[i][1] = ind+1
        print(ume(l[i][0])+ume(l[i][1]))





if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]
import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

def ume(x):
    x = str(x)
    if len(x) < 6:
        return '0'*(6-len(x)) + x
    return x

def main():
    N, M = mi()
    '''
    l = dp2(0, 3, M)
    cnt = [0]*(N+1)
    ans = dp2(0, 2, M)
    for i in range(M):
        p, y = mi()
        l[i][0], l[i][1], l[i][2] = p-1, y, i
        cnt[p] += 1
    for i in range(N):
        cnt[i+1] += cnt[i]

    l.sort(key=lambda x: x[0])
    for i in range(N):
        ichibu = l[cnt[i]:cnt[i+1]]
        ichibu.sort(key=lambda x: x[1])
        for j in range(cnt[i+1]-cnt[i]):
            ans[ichibu[j][2]][0] = ichibu[j][0]+1
            ans[ichibu[j][2]][1] = j+1
    
    for x, y in ans:
        print(ume(x)+ume(y))
    '''

    l = li2(M)
    pos = [[] for _ in range(N+1)]
    ans = dp2(0, 2, M)

    for a, b in l:
        pos[a].append(b)
    for a in pos:
        a.sort()
    for i, a in enumerate(l):
        ind = bisect.bisect_left(pos[a[0]], a[1])
        l[i][1] = ind+1
        print(ume(l[i][0])+ume(l[i][1]))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

def ume(x):
    x = str(x)
    if len(x) < 6:
        return '0'*(6-len(x)) + x
    return x

def main():
    N, M = mi()

    l = dp2(0, 3, M)
    cnt = [0]*(N+1)
    ans = dp2(0, 2, M)
    for i in range(M):
        p, y = mi()
        l[i][0], l[i][1], l[i][2] = p-1, y, i
        cnt[p] += 1
    for i in range(N):
        cnt[i+1] += cnt[i]

    l.sort(key=lambda x: x[0])
    for i in range(N):
        ichibu = l[cnt[i]:cnt[i+1]]
        ichibu.sort(key=lambda x: x[1])
        for j in range(cnt[i+1]-cnt[i]):
            ans[ichibu[j][2]][0] =ichibu[j][0]+1
            ans[ichibu[j][2]][1] =j+1
    
    for x, y in ans:
        print(ume(x)+ume(y))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import bisect as bis
n, m = map(int, input().split())
p, y = [], []
idx = lambda x: x-1
for _ in range(m):
    p_, y_ = map(int, input().split())
    p.append(p_)
    y.append(y_)
val = [[] for _ in range(n)]
for i in range(m):
    val[idx(p[i])].append(y[i]) # 市を県に対応づけるリスト
for i in range(n):  # ソートする
    val[i].sort()
for i in range(m):
    v = p[i]
    id = bis.bisect_right(val[idx(v)], y[i])  # 順番から、idをつける
    print(str(v).zfill(6) + str(id).zfill(6))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
p = []
for i in range(M):
    tmp = list(map(int, input().split()))
    tmp.append(i)
    p.append(tmp)
p.sort()
ans = []
count = 1
for i in range(M):
    if p[i-1][0] != p[i][0]:
        count = 1
    elif i != 0:
        count += 1
    id = str(p[i][0]).zfill(6)+str(count).zfill(6)
    ans.append((p[i][2],id))
ans.sort()
for i in ans:
    print(i[1])

Submission status: Accepted

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

iPY.sort(key=lambda x: x[2])
ans = []
for i, p, y in iPY:
    name = str(p).zfill(6) + str(pref[p]).zfill(6)
    ans.append((i, name))
    pref[p] += 1

ans.sort(key=lambda x: x[0])
for _, name in ans:
    print(name)

Submission status: Accepted

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

def kansu(N,M,S):

    S_tmp=[]
    for i in range(M):
        tmp = [int(S[i][0]),int(S[i][1]),0,i]
        S_tmp.append(tmp) 
    S_tmp.sort()
    tmp = S_tmp[0][0]
    cnt = 1

    for i in range(M):
        if tmp == int(S_tmp[i][0]):
            S_tmp[i][2] = cnt
            cnt += 1
        else :
            tmp = S_tmp[i][0]
            S_tmp[i][2] = 1
            cnt = 2
#    print(S_tmp)
    S_tmp = sorted(S_tmp, key=lambda x: x[3])
#    print(S_tmp)
    for i in range(M):
        print(str(S_tmp[i][0]).zfill(6),str(S_tmp[i][2]).zfill(6),sep='')
    



    # for m1 in range(M):
    #     cnt = 1
    #     tmp_m1 = S[m1][0]
    #     tmp_m2 = S[m1][1]
    #     for m2 in range(M):
    #         if S[m2][0] == tmp_m1 and S[m2][1] < tmp_m2:
    #             cnt = cnt + 1
    #     print(str(S[m1][0]).zfill(6),str(cnt).zfill(6),sep='')


N,M,S = nyu()
kansu(N,M,S)
#print(S)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
ipyx=[]
for _ in range(m):
  p_,y_ = map(int,input().split())
  ipyx.append([_+1,p_,y_,0])
"""
2 3
1 32
2 63
1 12
->
000001000002
000002000001
000001000001

2 3
2 5
2 77
2 99
->
000002000001
000002000002
000002000003
"""
# ipyx = [i,p,y,x]
A=[1]*(n+1)
ipyx.sort(key=lambda x:x[2])
for j in ipyx:
  j[3] = A[j[1]]
  A[j[1]] += 1
ipyx.sort(key=lambda x:x[0])
for j in ipyx:
  print(('00000'+str(j[1]))[-6:]+('00000'+str(j[3]))[-6:])

Submission status: Accepted

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

for i in range(M):
  pyi.append(list(map(int, input().split())))
  pyi[i].append(i)
  
N_cnt = [0] * N

pyi = sorted(pyi, key=lambda x:x[1])

for i in range(M):
  p = pyi[i][0]
  N_cnt[p-1] += 1
  pyi[i][0] = str(p).zfill(6)
  pyi[i][1] = str(N_cnt[p-1]).zfill(6)
  
pyi = sorted(pyi, key=lambda x:x[2])

for i in range(M):
  print(pyi[i][0] + pyi[i][1])

Submission status: Accepted

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

for i in range(M):
    P_Y_I[i].append(i+1)

P_Y_I = sorted(P_Y_I, key=lambda x:x[1])

N_count = [0 for k in range(N)]
for i in range(M):
    p = P_Y_I[i][0]
    N_count[p-1] += 1
    P_Y_I[i][0] = str(p).zfill(6)
    P_Y_I[i][1] = str(N_count[p-1]).zfill(6)

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

for i in range(M):
    print(P_Y_I[i][0]+P_Y_I[i][1])

Submission status: Accepted

Solution code:
import sys
IS = lambda: sys.stdin.readline().rstrip()
II = lambda: int(IS())
MII = lambda: list(map(int, IS().split()))
from bisect import bisect_left as bl

def main():
    n, m = MII()
    py = [tuple(MII()) for _ in range(m)]
    py_dict = dict(zip(range(10**5+1), [[0] for _ in range(10**5+1)]))
    for p, y in py: py_dict[p].append(y)
    for p, yy in py_dict.items():
        if yy != [0]: yy.sort()
    for p, y in py:
        idx = bl(py_dict[p], y)
        print(str(p).zfill(6)+str(idx).zfill(6))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

N, M=map(int, input().split())
#A=[]
Y=[[] for _ in range(N)] #県
for i in range(M):
  p,y=map(int, input().split())
  #A.append((p,y))
  Y[p-1].append([y,i+1])

for i in range(N):
  if Y[i]:
    Y[i].sort(key=lambda x: x[0])
#indexは時間かかる
ans=[]
for i in range(N):
  for j,L in enumerate(Y[i]):
    p,y,n=i+1, L[0],L[1]
    ans.append((n,p,j+1))
ans=sorted(ans)
for n,p,y in ans:
  a=(6-len(str(p)))*"0"+str(p)+(6-len(str(y)))*"0"+str(y)
  print(a)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
pref_year = [[] for _ in range(n+1)]
for i in range(1,m+1):
    p,y = map(int,input().split())
    pref_year[p].append((y,i))
ans = []
for p,li in enumerate(pref_year):
    if li:
        li.sort()
        for num,j in enumerate(li):
            ans.append((j[1],str(p).zfill(6)+str(num+1).zfill(6)))
ans.sort()
for i in ans:
    print(i[1])

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
base_1 = []
key = {}
ans_str = []
ans_n = []

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

for i in range(m):
  p_str = str(base_1[i][0])
  len_p = len(list(p_str))
  temp = "p"+p_str
  
  if temp not in key:
    key[temp] = 1
    count = str(1)
  else :
    a = key[temp]
    key[temp] = a + 1
    count = str(key[temp])
    
  len_count = len(list(count))
  
  for j in range(6-len_p):
    p_str = "0" + p_str
    
  for j in range(6-len_count):
    count = "0" + count
    
  base_1[i].append(p_str + count)
    
base_1.sort(key = lambda x:x[2])

for i in range(m):
  print(base_1[i][3])

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)
dic = {}
for i in range(n):
	b[i].sort()
	for j,k in enumerate(b[i]):
		dic[k] = j+1

for i, j in a:
	print ("{:06d}".format(i) + "{:06d}".format(dic[j]))

Submission status: Accepted

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

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

prefecture=[[] for _ in range(N)]
for el in PY:
    p, y, num = el
    prefecture[p-1].append((y, num))
#print(prefecture)

ans=[None]*M
for j, p in enumerate(prefecture):
    for i, city in enumerate(p):
        ans[city[1]] = str(j+1).zfill(6) + str(i+1).zfill(6)
#print(ans)
for val in ans:
    print(val)

Submission status: Accepted

Solution code:
from collections import namedtuple, defaultdict
from bisect import bisect

City = namedtuple('City', 'y p')

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

cities = []
cities_by_P = defaultdict(list)

for _ in range(M):
  p, y = map(int, input().split())
  city = City(y, p)
  cities.append(city)
  cities_by_P[p].append(city)
  
for p in cities_by_P.keys():
  cities_by_P[p].sort()

# MlogM  
for city in cities:
  i = bisect(cities_by_P[city.p], city)
  print('%06d' % city.p + '%06d' % 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([i,p,y])
ans=['']*M
PY1=sorted(PY,key=lambda x:x[2])
dict={}
for i in range(M):
  ans[PY1[i][0]]+=str(PY1[i][1]).zfill(6)
  if not (PY1[i][1] in dict):
    ans[PY1[i][0]]+='1'.zfill(6)
    dict[PY1[i][1]]=1
  else:
    ans[PY1[i][0]]+=str(int(dict[PY1[i][1]])+1).zfill(6)
    dict[PY1[i][1]]+=1
for i in range(M):
  print(ans[i])

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
d=[0]*M
res = []
for i in range(M):
    P,Y = map(int,input().split())
    res.append((P,Y,i))
c=0
res.sort()
t = str(res[0][0])
for i in res:
    x = str(i[0])
    if x == t:
        c+=1
    else:
        c=1
        t = x
    d[i[2]] = (6-len(x))*'0'+x+(6-len(str(c)))*'0'+str(c)

for i in d:
    print(i)