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:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, M = MAP()
YPC = []
for c in range(M):
    p, y = MAP()
    p -= 1
    YPC.append((y, p, c))

YPC.sort()
ans = [()] * M
pcnt = [0] * N
for _, p, c in YPC:
    ans[c] = (p + 1, pcnt[p] + 1)
    pcnt[p] += 1

for p, c in ans:
    print(str(p).zfill(6) + str(c).zfill(6))

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


ans = [0 for i in range(M)]
c = 1
d = 0
for i in range(M):
    
    if c == PY[i][0]:
        d += 1
    else:
        c = PY[i][0]
        d = 1
    ans[PY[i][2]] = '0'*(6-len(str(PY[i][0])))  + str(PY[i][0]) + '0'*(6-len(str(d))) + str(d)
for i in ans:
    print(i)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
A = [[] for i in range(N+1)]
B = []
d = {}
for i in range(M):
    p,y = map(int,input().split())
    B.append((p,y))
    A[p].append(y)
for i in range(N+1):
    A[i].sort()
    n = len(A[i])
    for j in range(n):
        d[A[i][j]] = j+1
for i in range(M):
    p,y = B[i]
    q = d[y]
    m = 6 - len(str(p))
    n = 6 - len(str(q))
    ans = "0"*m + str(p) + "0"*n + str(q)
    print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
shi = []
for i in range(m):
  pi, yi = map(int, input().split())
  shi.append([i, pi, yi])
  
shi.sort(key=lambda x:x[1:])
# print(shi)
x = 0
for i in range(m):
  x += 1
  shi[i].append("{:06d}{:06d}".format(shi[i][1], x))
  if i != m-1 and shi[i][1] != shi[i + 1][1]:
    x = 0
shi.sort(key=lambda x:x[0])
for i in range(m):
  print(shi[i][3])

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
P_Y_list = [list(map(int, input().split())) + [i] for i in range(M)]
P_Y_list.sort(key=lambda x: x[1])
count_P = [0] * (N+1)

# print(P_Y_list)
for idx, p_y in enumerate(P_Y_list):
    p = p_y[0]
    y = count_P[p_y[0]] + 1
    ans = str(p).zfill(6) + str(y).zfill(6)
    p_y += [ans]

    count_P[p_y[0]] += 1

P_Y_list.sort(key=lambda x: x[2])
for p_y in P_Y_list:
    print(p_y[3])

Submission status: Accepted

Solution code:
from sys import stdin
import bisect

def fetch_one_line():
    return stdin.readline().rstrip()


def fetch_int_input():
    return [int(s) for s in fetch_one_line().split()]


def fetch_inputs(times):
    return [fetch_one_line() for _ in range(times)]


def fetch_int_inputs(times):
    return [fetch_int_input() for _ in range(times)]


PREF, YEAR = 0, 1

N, M = fetch_int_input()
data = fetch_int_inputs(M)

pre_save = [[] for _ in range(N)]
for d in data:
    pre_save[d[PREF] - 1].append(d[YEAR])

for p in pre_save:
    p.sort()


def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect.bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    raise ValueError


for d in data:
    left = str(d[PREF]).zfill(6)
    right = str(index(pre_save[d[PREF] - 1], d[YEAR]) + 1).zfill(6)
    print(left+right)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
py = []
s = '000000'
for i in range(m):
    p, y = map(int, input().split())
    py.append([p, y, i])
py.sort(key=lambda py:(py[0],py[1]))

py[0].append(1)
for i in range(m-1):
    a = 1
    if py[i][0] == py[i+1][0]:
        py[i+1].append(py[i][3]+1)
    else:
        py[i+1].append(1)
        
py.sort(key=lambda py:(py[2]))

for j in range(len(py)):
    print((s+str(py[j][0]))[-6:]+(s+str(py[j][3]))[-6:])

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
Y=[0]*m
P=[0]*m
for i in range(m):
    P[i],Y[i]=map(int,input().split())
yp=list(zip(Y,P,range(m)))
yp.sort()
underdigit=[0]*(n+1)
ans=[""]*m
for y,p,i in yp:
    underdigit[p]+=1
    ans[i]="%06d%06d" %(p,underdigit[p])
for a in ans:
    print(a)

Submission status: Accepted

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

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

lst2 = []
pref = 0
for v in lst:
    if pref != v[0]:
        cnt = 1
        pref = v[0]
    lst2.append(['{:0=6}{:0=6}'.format(v[0], cnt), v[2]])
    cnt += 1
lst2.sort(key=lambda x: x[1])

[print(lst2[i][0]) for i in range(m)]

Submission status: Accepted

Solution code:
import sys
import numpy as np
input = sys.stdin.readline
N, M = [int(x) for x in input().split()]
PY = [[int(x) for x in input().split()] for _ in range(M)]
for j in range(M):
    PY[j].append(j)
PY.sort()
A = [1] * (N+1)
ans = ["s"] * M
for i in range(M):
    temp = PY[i]
    P, Y = temp[0], temp[1]
    a = str(P).zfill(6)
    b = str(A[P]).zfill(6)
    A[P] += 1
    ans[temp[2]] = a + b
for k in ans:
    print(k)

Submission status: Accepted

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

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

for i in range(N):
  L[i]=sorted(L[i], reverse=False, key=lambda x: x[1])
  for j in range(len(L[i])):
    ans[L[i][j][0]]=[i,j]
    
for i in range(M):
  a = str(ans[i][0]+1).zfill(6)+str(ans[i][1]+1).zfill(6)
  print(a)

Submission status: Accepted

Solution code:
import bisect
N, M = (int(i) for i in input().split()) 
PY = [[int(i) for i in input().split()] for i in range(M)] 
D = [[] for _ in range(N)]

for i, (p, y) in enumerate(PY):
  D[p-1].append((y, i))

ans = [None] * M
output = [[] for _ in range(M)]
for i, d in enumerate(D):
  d.sort()
  for k, (y, j) in enumerate(d):
    ans[j] = (i, k)

for i, k in ans:
  print('{}{}'.format(str(i+1).zfill(6), str(k+1).zfill(6)))

Submission status: Accepted

Solution code:
import sys
from operator import itemgetter
sys.setrecursionlimit(10**6)
if sys.platform in (['ios','darwin','win32']):
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

N, M = MAP()
Cities = []
for i in range(M):
	Cities.append([i, MAP()])

Pref = [[] for _ in range(N)]
#print(Cities)
#print(Pref)

for c in Cities:
	i, [p, y] = c
	Pref[p-1].append([y, i])

for p in Pref:
	p.sort()
#print(Pref)

ans = []
for i,p in enumerate(Pref):
	for j in range(len(p)):
		ans.append([p[j][1] ,str(i+1).zfill(6)+str(j+1).zfill(6)])
ans.sort()

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n,m = list(map(int,input().split()))
d = [[i,tuple(map(int,input().split()))] for i,_ in enumerate(range(m))]
#print(d)

d.sort(key=lambda x:x[1][1])
p_cnt = [0] * (n+1)
ret_tuples = [0] * m #(市id,認識番号) のtupleのリスト

for i,v in enumerate(d):
    p = v[1][0]
    x = p_cnt[p]+1
    p_cnt[p]+=1
    ret_tuples[i] = (v[0],"{:0=6}{:0=6}".format(p,x))

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

Submission status: Accepted

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

queue = sorted(queue)

index = 0
keep = queue[0][0]
for i in range(m):
    if keep != queue[i][0]:
        index = 0
        keep = queue[i][0]
    index += 1
    queue[i][0] = str(queue[i][0]).zfill(6)
    queue[i][1] = str(index).zfill(6)

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

for data in queue:
    cn, yn, i = data
    print(cn + yn)

Submission status: Accepted

Solution code:
n, m = map(int, raw_input().split())
prefecs = [[] for i in range(n+1)]
queries = []
for _ in range(m):
    p, y = map(int, raw_input().split())
    queries.append((p, y))
    prefecs[p].append(y)
for i in range(1, n+1):
    prefecs[i].sort()
dic_list = [{} for i in range(n+1)]
for i in range(1, n+1):
    for j in range(len(prefecs[i])):
        dic_list[i][prefecs[i][j]] = j+1
for p, y in queries:
    print "%06d%06d" % (p, dic_list[p][y])

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()
ans = [0 for i in range(M)]
count = 0
old = 0
for j in range(M):
    p,y,inum = PY[j]
    if old == p:
        pnum = p
        cnum = count
    else:
        old = p
        count = 1
        pnum = p
        cnum = 1

    count += 1
    pnum = str(pnum)
    cnum = str(cnum)
    ans[inum] = '0'*(6-len(pnum)) + pnum + '0'*(6-len(cnum)) + cnum

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

Submission status: Accepted

Solution code:
from collections import defaultdict
d = defaultdict(list)
n, m = map(int, input().split())
l = [0]*m
for i in range(m):
  p, y = map(int, input().split())
  d[p].append((y, i))
for p, b in d.items():
  b.sort()
  for i in range(len(b)):
    s, t = b[i]
    l[t] = "0"*(6-len(str(p))) + str(p) + "0"*(6-len(str(i+1))) + str(i+1)
print(*l, sep="\n")

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
L=[[0 for i in range(4)]for i in range(M)]
for i in range(M):
    a,b=map(int,input().split())
    L[i][0]=i
    L[i][1]=a
    L[i][2]=b
L2=sorted(L,key= lambda x: (x[1],x[2]))

c=0
t=0
for i in range(M):
    if(L2[i][1]!=c):
        c=L2[i][1]
        t=1
    L2[i][3]=t
    t+=1

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

for i in range(M):
    print('{0:06d}'.format(L3[i][1]),'{0:06d}'.format(L3[i][3]),sep="")

Submission status: Accepted

Solution code:
from collections import defaultdict
N,M=map(int,input().split())
PD=defaultdict(lambda: [])
OR=dict()
ANS=dict()
for i in range(M):
    p, y=map(int,input().split())
    OR[i] = (p,y)
    PD[p].append(y)

for k in PD.keys():
    l=sorted(PD[k])
    for i,n in enumerate(l):
        ANS[(k,n)] = str(k).zfill(6) + str(i+1).zfill(6)
for k in OR.values():
    print(ANS[k])

Submission status: Accepted

Solution code:
from collections import defaultdict
N, M = [int(val) for val in input().split(' ')]
P, Y = [], []


def complete_val(val):
    length = len(str(val))
    prefix = '0' * (6 - length)
    return prefix + str(val)


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

cities = defaultdict(dict)
for i in range(M):
    cities[P[i]][i] = Y[i]

results = {}
for p, p_cities in cities.items():
    p_str = complete_val(p)
    for city_rank, (m_index, year) in enumerate(sorted(p_cities.items(), key=lambda x: x[1])):
        city_str = complete_val(city_rank+1)
        results[m_index] = p_str + city_str

for m_index, string in sorted(results.items(), key=lambda x: x[0]):
    print(string)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
PY=[list(map(int,input().split())) for _ in range(M)]
idx=sorted(range(M),key=lambda x:PY[x][1])
PY.sort(key=lambda x:x[1])
flag=[1]*N
keep=[]
for P,Y in PY:
  keep.append(str(P).zfill(6)+str(flag[P-1]).zfill(6))
  flag[P-1]+=1
  
ans=[0]*M
for i,k in zip(idx,keep):
  ans[i]=k
  
for a in ans:
  print(a)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,m = inpl()
p = []
res = [[] for i in range(m)]
for i in range(m):
    a,b = inpl()
    p.append((a,b,i))
p.sort()
cnt = 0
tmp = 0
for i,j in enumerate(p):
    if i == 0:
        tmp = j[0]
    if tmp == j[0]:
        cnt += 1
    else:
        tmp = j[0]
        cnt = 1
    res[j[2]] = [j[0],cnt] 
for i in res:
    print('{}{}'.format(str(i[0]).zfill(6),str(i[1]).zfill(6)))

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,m = inpl()
p = []
res = [[] for i in range(m)]
for i in range(m):
    a,b = inpl()
    p.append((a,b,i))
p.sort(key=lambda x:x[1])
p.sort(key=lambda x:x[0])
cnt = 0
tmp = 0
for i,j in enumerate(p):
    if i == 0:
        tmp = j[0]
    if tmp == j[0]:
        cnt += 1
    else:
        tmp = j[0]
        cnt = 1
    res[j[2]] = [j[0],cnt] 
for i in res:
    print('{}{}'.format(str(i[0]).zfill(6),str(i[1]).zfill(6)))

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,m = inpl()
py = [inpl() for i in range(m)]
p = [[] for i in range(n+5)]
res = defaultdict(lambda : defaultdict(int))
for i,j in enumerate(py):
    p[j[0]].append(j[1])
for k,i in enumerate(p):
    i.sort()
    for j,_ in enumerate(i):
        res[k][i[j]] = j+1
for i in py:
    print('{0}{1}'.format(str(i[0]).zfill(6),str(res[i[0]][i[1]]).zfill(6)))

Submission status: Accepted

Solution code:
#C
N,M = map(int,input().split())
PY = []

for i in range(M):
    p,y = map(int,input().split())
    PY.append([p,y,i])
    
ans = 0
PY.sort()
ans = ["" for i in range(M)]
count = 0
old = 0
for py in PY:
    p,y,i = py
    if old == p:
        city = p
        num = count
        sc = str(city)
        sn = str(num)
        while len(sc) < 6:
            sc = "0"+sc
        while len(sn) < 6:
            sn = "0"+sn
        ans[i] = sc+sn
        count+=1
    else:
        count = 1
        old = p
        city = p
        num = count
        sc = str(city)
        sn = str(num)
        while len(sc) < 6:
            sc = "0"+sc
        while len(sn) < 6:
            sn = "0"+sn
        ans[i] = sc+sn
        count+=1
        
for i in range(M):
    print(ans[i])

Submission status: Accepted

Solution code:
from collections import defaultdict
from bisect import bisect
N,M,*P = map(int,open(0).read().split())
d = defaultdict(list)
Z = set()
for n,m in zip(*[iter(P)]*2):
    d[n].append(m)
    Z.add(n)
for z in Z:
    d[z].sort()
for n,m in zip(*[iter(P)]*2):
    print(str(n).zfill(6)+str(bisect(d[n],m)).zfill(6))

Submission status: Accepted

Solution code:
# http://drken1215.hatenablog.com/entry/2019/03/21/234900
# 写経

def main():
    from bisect import bisect_left
    import sys

    input = sys.stdin.readline

    n, m = map(int, input().split())
    PY = []
    e = [[] for _ in range(n + 1)]
    for _ in range(m):
        _p, _y = map(int, input().split())
        e[_p].append(_y)
        PY.append((_p, _y))

    for idx in range(n + 1):
        e[idx] = tuple(sorted(set(e[idx])))

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# http://drken1215.hatenablog.com/entry/2019/03/21/234900
# 写経

from bisect import bisect_left

n, m = map(int, input().split())
PY = []
e = [[] for _ in range(n + 1)]
for _ in range(m):
    _p, _y = map(int, input().split())
    e[_p].append(_y)
    PY.append((_p, _y))

for idx in range(n + 1):
    e[idx] = tuple(sorted(set(e[idx])))

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

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
X=[]
for i in range(M):
  p,y = map(int,input().split())
  X +=[[i,p,y,0]]
X=sorted(X,key=lambda x:x[2])
R=[0]*(N+1)
for i in range(M):
  X[i][3]=R[X[i][1]]+1
  R[X[i][1]] += 1
X=sorted(X,key=lambda x:x[0])
for i in range(M):
  id_A='0'*(6-len(str(X[i][1])))+str(X[i][1])
  id_B='0'*(6-len(str(X[i][3])))+str(X[i][3])
  print(id_A+id_B)

Submission status: Accepted

Solution code:
import heapq
n,m=map(int,input().split())
a=[0]*n
b=[]
c=[]

#
def make_num_str_pair(s):
    return str(s[0]).zfill(6)+str(s[1]).zfill(6)
#heapqで年の順番にして突っ込んで、その順で取り出して該当のaの要素を+して、strでzfill使いながらくっつける

for i in range(m):
    p,y=map(int,input().split())
    b.append([p,y,i])
b.sort(key=lambda x: x[1])
for i in range(m):
    a[b[i][0]-1]+=1
    b[i][1]=a[b[i][0]-1]
b.sort(key=lambda x: x[2])
for i in range(m):
    print(make_num_str_pair(b[i]))

Submission status: Accepted

Solution code:
from bisect import bisect_left
N,M = map(int,input().split())
PtoY = [[] for n in range(N)]
check = []
for m in range(M):
    P,Y = map(int,input().split())
    PtoY[P-1].append(Y)
    check.append([P,Y])
for n in range(N):
    PtoY[n].sort()
for m in range(M):
    p,y = check[m][0],check[m][1]
    a = bisect_left(PtoY[p-1],y)+1
    string = str(p).zfill(6) + str(a).zfill(6)
    print(string)

Submission status: Accepted

Solution code:
import math
import collections
import itertools
import sys
import bisect
from heapq import heappop,heappush,heapify
sys.setrecursionlimit(10**6)
def MAP(): return list(map(int,input().split()))
def INT(): return int(input())
def FLOAT(): return float(input())
MOD = 10**9+7

N,M = MAP()
Y = [0]*(10**5)
P = [0]*(10**5)
yd =[[] for _ in range(N)]
for i in range(M):
    p,y = MAP()
    P[i] = p-1
    Y[i] = y
    yd[p-1].append(y)

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

for i in range(M):
    print("{0:06d}".format(P[i]+1),end="")
    print("{0:06d}".format(bisect.bisect_left(yd[P[i]],Y[i])+1))

Submission status: Accepted

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

ans=sorted(ans,key=lambda x:x[1])
for k in range(m):
    print(ans[k][0])

Submission status: Accepted

Solution code:
from copy import deepcopy as dp
from operator import itemgetter as ig
n,m = map(int,input().split())
#[input番号,県番号,年,県における順番]
list1 = []
for i in range(m):
    list1.append([i] + list(map(int,input().split())))

list2 = dp(list1)
list2.sort(key=ig(1,2))
city_number = 0
list2[0].append(city_number)
for i in range(1,m):
    if list2[i][1] == list2[i-1][1]:
        city_number += 1
        list2[i].append(city_number)
    else:
        city_number = 0
        list2[i].append(city_number)
list2.sort(key=ig(0))
for i in range(m):
    print("{0:06d}".format(list2[i][1])+"{0:06d}".format(list2[i][3]+1))

Submission status: Accepted

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

for i in range(M):
    data.append([i]+list(map(int,input().split())))

count = [0] * (N+1)

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

ans = [0] * M

for i in range(M):
    count[data[i][1]] += 1
    y = [0] * (6-len(list(str(data[i][1])))) + list(str(data[i][1]))
    z = [0] * (6-len(list(str(count[data[i][1]])))) + list(str(count[data[i][1]]))
    ans[data[i][0]] = list(map(int,y + z))

#print(ans)
for i in range(M):
    print("".join(map(str,ans[i])))

Submission status: Accepted

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

prefecture = [[] for i in range(n)]
li = []

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

for i in prefecture:
    i.sort()

for i in li:
    a = i[0]-1
    b = i[1]
    index = bisect.bisect_left(prefecture[a], b) + 1
    print(str(i[0]).zfill(6)+str(index).zfill(6))

Submission status: Accepted

Solution code:
from operator import itemgetter
N , M = map(int, input().split(' '))

city = []
for i in range(M):
    a, b = map(int, input().split(' '))
    city.append([a, b, i])

city_y = sorted(city, key = itemgetter(1))
city_num = [0 for _ in range(N+1)]
city_ID = {}

for i in range(M):
    city_num[city_y[i][0]] += 1
    city_ID[city_y[i][2]] = ("{:0=6}{:0=6}".format(city_y[i][0], city_num[city_y[i][0]]))

for i, j in sorted(city_ID.items()):
    print(j)

Submission status: Accepted

Solution code:

from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations
import sys
import bisect
import string
import math
import time
#import random


def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return [int(i) for i in input().split()]
def LI_(): return [int(i)-1 for i in input().split()]
def StoI(): return [ord(i)-97 for i in input()]
def ItoS(nn): return chr(nn+97)
def input(): return sys.stdin.readline().rstrip()

def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)

YN = ['Yes', 'No']
MOD = 10**9+7
inf = float('inf')
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)


show_flg = False
# show_flg = True

def main():
    N, M = MI()
    cities = [None] * M
    identifiers = [1] * (N + 1)
    output = [None] * M

    for i in range(M):
        P, Y = MI()
        cities[i] = (Y, P, i)

    cities.sort()
    show(cities)

    for i in range(M):
        Y, P, idx = cities[i]
        output[idx] = str(P).zfill(6) + str(identifiers[P]).zfill(6)
        identifiers[P] += 1

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
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(key = lambda x: (x[0], x[1]))
table = [0] * (N + 1)
res = [None] * M
for i in range(M):
  p, y, j = c[i]
  table[p] += 1
  res[j] = str(p).zfill(6) + str(table[p]).zfill(6)
for i in range(M):
  print(res[i])

Submission status: Accepted

Solution code:
a,b = map(int,input().split())
li = []
for i in range(b):
    li.append(input().split())
for i in range(b):
    li[i] = [int(x) for x in li[i]]
    li[i].append(i+1)
li.sort()
L = []
for i in range(a):
    L.append([])
for i in range(b):
    L[li[i][0]-1].append((li[i][0],li[i][1],li[i][2]))
ans = []
for i in range(a):
    for j in range(len(L[i])):
        ans.append((L[i][j][0],j+1,L[i][j][2]))
ans.sort(key = lambda x:x[2])
for i in range(b):
    print(str(ans[i][0]).zfill(6)+str(ans[i][1]).zfill(6))

Submission status: Accepted

Solution code:
from operator import itemgetter
 
N, M = map(int,input().split())
data = [[int(i) for i in input().split()] for j in range(M)]
 
# 市iの(i-1)を先頭に追加
for i in range(M):
    data[i].insert(0,i)
 
# 県でソートしてから誕生年でソート
data.sort(key=itemgetter(1,2))
 
# answer[0]: 市iの(i-1)
# answer[1]: 認識番号
answer = [[0,0] for i in range(M)]
x = 1
# 認識番号を割り当てる
for i in range(M):
    answer[i][0] = data[i][0]
    if data[i][1] != data[i-1][1]:
        x = 1
    answer[i][1] = data[i][1]*1000000 + x
    x += 1
 
# 入力順に出力する
answer.sort(key=itemgetter(0))
for _,i in answer:
    print(str(i).rjust(12,"0"))

Submission status: Accepted

Solution code:
import sys
from collections import deque
input = sys.stdin.readline

N, M = [int(x) for x in input().strip().split()]
NL = [deque([]) for n in range(10 ** 5)]

IN = [0] * M
d = {}
for m in range(M):
    IN[m] = tuple([int(x) for x in input().strip().split()]) 

for p, y in IN:
    NL[p-1].append(y)

for p, nl in enumerate(NL, start=1):
    d[p] = {}
    for i, n in enumerate(sorted(nl), start=1):
        d[p][n] = i

for p, y in IN:
    print('{:06d}{:06d}'.format(p, d[p][y]))

Submission status: Accepted

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

DEBUG = False

dbgp = print if DEBUG else lambda *x:x

rank = dict()
counter = dict([i, 1] for i in range(1, N + 1))
for p, y in sorted(PY, key= lambda x:x[1]):
    rank[y] = counter[p]
    counter[p] += 1

dbgp('rank : ', rank)
dbgp('counter : ', counter)

for p, y in PY:
    print('{0:06}{1:06}'.format(p, rank[y]))

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
info=[None]*M
pre=[None]*(N+1)
for i in range(M):
  p,y=map(int,input().split())
  info[i]=[p,y]
  if pre[p]==None:
    pre[p]=[y]
  else:
    pre[p].append(y)
    
for i in range(1,len(pre)):
  cities=pre[i]
  if cities==None:
    continue
  cities=sorted(cities)
  dic={}
  for j in range(len(cities)):
    dic[cities[j]]=j+1
  pre[i]=dic
  
for i in range(len(info)):
  p=info[i][0]
  y=info[i][1]
  print(str(p).zfill(6)+str(pre[p][y]).zfill(6))

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
x = [list(map(int,input().split())) for _ in range(M)]
new=[]
inf  = [u for u in range(1,N+1)]
ref = 0
for i in range(M):
  x[i].insert(0,i)
x.sort(key=lambda y: y[2])
x.sort(key=lambda y: y[1])

for q in inf:
  count = 1
  for p in range(ref,M):
    if x[p][1]!=q:
      ref=p
      break
    new.append([x[p][0],x[p][1]*1000000+(count)])
    count += 1
new.sort()
for z in range(M):
  takahasi = "%012d" % new[z][1]
  print(takahasi)

Submission status: Accepted

Solution code:
from collections import defaultdict
def inpl(): return list(map(int,input().split()))

class CountUp:
    def __init__(self, start=0):
        self.index = start-1

    def __call__(self):
        self.index += 1
        return self.index

ui = defaultdict(CountUp())
plist = []
clists = []
Np = 0

N, M = inpl()
P = [0]*M
Y = [0]*M
for i in range(M):
    P[i], Y[i] = inpl()
    p = ui[P[i]]
    if p >= Np:
        plist.append(P[i])
        clists.append([[i,Y[i]]])
        Np += 1
    else:
        clists[p].append([i,Y[i]])

ids = ['']*M
for p in range(Np):
    clists[p].sort(key=lambda x: x[1])
    for c in range(len(clists[p])):
        cid = "{0:06d}".format(plist[p]) + "{0:06d}".format(c+1)
        ids[clists[p][c][0]] = cid

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

Submission status: Accepted

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

py_map = {}
x = 1
prep = 0
for p, y in sorted(PY):
    if prep == p:
        x += 1
    else:
        x = 1
    py_map[(p,y)] = str(p).zfill(6) + str(x).zfill(6)
    prep = p

for p, y in PY:
    print(py_map[(p, y)])

Submission status: Accepted

Solution code:
from collections import defaultdict
from bisect import bisect

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

city = []

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

dic = defaultdict(list)
for p, y in sorted(city):
    dic[p] += [y]

# print(sorted(city))
# print(dic)

for p, y in city:
    x = bisect(dic[p], y)
    print("{0:06d}{1:06d}".format(p, x))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

from collections import namedtuple
from operator import attrgetter

City = namedtuple("City", "ID, pref, year")

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

Cities = []
for ID in range(M):
    pref, year = map(int, input().split())
    Cities.append(City(ID, pref, year))

def get_sID(Cities):
    temp = Cities.copy()

    temp.sort(key=attrgetter("year"))
    temp.sort(key=attrgetter("pref"))

    lid = 1
    currentPref = None
    for City in temp:
        if currentPref != City.pref:
            currentPref = City.pref
            lid = 1

        yield City.ID, "{0:0>6}{1:0>6}".format(City.pref, lid)
        lid += 1

for _, sID in sorted(get_sID(Cities)):
    print(sID)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

d = defaultdict(int)
b = dict()

for p, y in sorted(years, key=lambda x: x[1]):
    d[p] += 1
    b[y] = '{:06d}{:06d}'.format(p, d[p])

for p, y in years:
    print(b[y])

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
d=[]
for i in range(m):
  d.append(list(map(int,input().split())))
  d[i].append(1)
s=sorted(d)
k=1
if m>1:
  for i in range(m-1):
    if s[i][0]==s[i+1][0]:
      s[i][2]=k
      s[i+1][2]=k+1
      k=k+1
    else:
      k=1
      s[i+1][2]=k
      
for i in range(m):
  ans=1000000000000+d[i][0]*1000000+d[i][2]
  print(str(ans)[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])

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

k=list(range(1,10**5+1))
v=[0]*10**5
cnt_dict=dict(zip(k,v))
arr=[]
for i,j,k in PY_sort:
    cnt_dict[j]+=1
    arr.append([i,str(j).zfill(6)+str(cnt_dict[j]).zfill(6)])

s = sorted(arr, key=lambda x: x[0])
for a,b in s:
    print(b)

Submission status: Accepted

Solution code:
n,m=[int(i) for i in input().split()]
py=[[int(i) for i in input().split()]+[_,""] for _ in range(m)]
kazu=[0]*(n+1)
py.sort(key=lambda x:x[1])
for i in range(m):
    kazu[py[i][0]]+=1
    py[i][3]+=str(kazu[py[i][0]])
py.sort(key=lambda x:x[2])
for i in range(m):
    print(str(py[i][0]).zfill(6)+py[i][3].zfill(6))