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=int(input())
n,m=map(int,input().split())
#hl=list(map(int,input().split()))
#l=[list(map(int,input().split())) for i in range(n)]

citydic={}

def make_id(p):
    dif=6-len(str(p))
    res="".join(["0" for i in range(dif)])
    return res+str(p)

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

#print(citydic)
id_dic={}

for pref, val in citydic.items():
    l=sorted(val,key=lambda x: x[2])
    for x,temp in enumerate(l,1):
        i,p,y=temp
        # make id
        cityid=make_id(p)+make_id(x)
        id_dic[i]=cityid

for i in range(1,m+1):
    print(id_dic[i])

Submission status: Accepted

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

new_pyn=sorted(pyn)

cnt=1
i=1
j=0


while(j<m):
    if new_pyn[j][0] == i:
        new_pyn[j].append(cnt)
        cnt+=1
        j+=1

    else:
        cnt=1
        i+=1
final=sorted(new_pyn,key=lambda x:x[2])


for i in range(m):
    a=str(final[i][0])
    b=str(final[i][3])
    print(str(a.zfill(6))+str(b.zfill(6)))

Submission status: Accepted

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

d={}
for i in range(m):
    p,y=map(int, input().split())
    if p not in d:
        d[p]=[[y,p,i]]
    else:
        d[p].append([y,p,i])

bango_list=['0']*m
for key in d:
    d[key].sort()
    for i in range(len(d[key])):
        p_bango=str(key).zfill(6)
        x_bango=str(i+1).zfill(6)
        bango_list[d[key][i][2]]=p_bango+x_bango

for b in bango_list:
    print(b)

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit
from bisect import bisect_left


def main():
    input = stdin.buffer.readline
    n, m = map(int, input().split())
    py = [list(map(int, input().split())) for _ in range(m)]

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

    for p, y in py:
        summary[p - 1].append(y)

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

    for p, y in py:
        print(str(p).zfill(6), str(bisect_left(summary[p - 1], y) + 1).zfill(6), sep='')


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict

n, m = map(int, input().split())
py = []
lst = [[] for _ in range(n)]
for _ in range(m):
    tmp = list(map(int, input().split()))
    py.append((tmp[0], tmp[1]))
    lst[tmp[0] - 1].append(tmp[1])
dic = {}
for i, l in enumerate(lst):
    l.sort()
    for j, num in enumerate(l):
        dic[(i + 1, num)] = "{:06}".format(i + 1) + "{:06}".format(j + 1)
for l in py:
    print(dic[l])

Submission status: Accepted

Solution code:
# Python3 (3.4.3)
import sys
input = sys.stdin.readline

# -------------------------------------------------------------
# function
# -------------------------------------------------------------


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

# 県ごとに分類
A = [[] for _ in range(N+1)]
for i in range(M):
    p,y = PY[i]
    A[p].append((y,i))

for i in range(1,N+1):
    A[i].sort()

Ans = [0]*M
for i in range(1,N+1):
    for j in range(len(A[i])):
        y,k = A[i][j]
        Ans[k] = "{:06d}{:06d}".format(i,j+1)

for ans in Ans:
    print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
d = [[] for _ in range(n)]
ans = [[] for _ in range(m)]
for i, _ in enumerate(range(m)):
    p, y = map(int, input().split())
    d[p-1].append([i, y])
for i in range(n):
    d[i].sort(key=lambda x:x[1])
    for j in range(len(d[i])):
        ans[d[i][j][0]].append(str(i+1).zfill(6)+str(j+1).zfill(6))
for i in ans: print(*i)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import bisect

"""
ABC113_C ID 学び：
 python の0埋め　s.rjust(digit,0) でいける
 sortを県ごとにしないといけない、とわかれば、input, sort , outputの３段かいに別れる
どんな配列を持てばいいかは事前に考える。
実際にそこまで立てて、inputをローカルでやると良い
"""

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
n, m = map(int, input().split())
lis_p = [[] for _ in range(n)]  # 県pに属する市の誕生年が入る
city = [[0, 0] for _ in range(m)]  # p と　idx
idx_p = []  # 何番目にそのcity が県pに追加されたかを記憶
# input
for i in range(m):
    p, y = map(int, input().split())
    city[i][0] = p - 1
    city[i][1] = y
    lis_p[p - 1].append(y)
for pref in range(n):
    k = len(lis_p[pref])
    # print(lis_p[pref])
    idx = []
    if k > 0:
        lis_p[pref], idx = zip(*sorted(zip(lis_p[pref], range(k))))
    idx_p.append(list(idx))
# print(lis_p, idx_p)
for i in range(m):
    # string になおす必要がある rjust
    print(str(city[i][0] + 1).rjust(6, "0"), end="")
    print(str(1 + bisect.bisect_left(lis_p[city[i][0]], city[i][1])).rjust(6, "0"))

Submission status: Accepted

Solution code:
from operator import itemgetter

def id(n):
    if len(str(n)) >= 6:
        return str(n)
    return "0"*(6-len(str(n)))+str(n)

n,m = map(int,input().split())
data = [[] for i in range(n+1)]
for i in range(m):
    p,y = map(int,input().split())
    data[p].append((i,y))
ans = []
for i in range(n+1):
    if data[i]:
        data[i].sort(key=itemgetter(1))
        for j in range(len(data[i])):
            ans.append((data[i][j][0],id(i)+id(j+1)))
ans.sort()
for i,j in ans:
    print(j)

Submission status: Accepted

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

x = {}

for i in range(len(PY)):
    prefecture = PY[i][0]
    year = PY[i][1]

    if prefecture in x.keys():
        x[prefecture].append((year, i))
    else:
        x[prefecture] = [(year, i)]

for i in x:
    x[i] = sorted(x[i])



for i in x:
    for t in range(len(x[i])):
        PY[x[i][t][1]] = str(i).zfill(6) + str(t + 1).zfill(6)

for py in PY:
    print(py)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

ids = {}
nums = defaultdict(int)
for i, p, y in IPY:
    nums[p] += 1
    ids[i] = '{:06d}{:06d}'.format(p, nums[p])
for i in range(1, M + 1):
    print(ids[i])

Submission status: Accepted

Solution code:
from operator import itemgetter
n,m=map(int,input().split())
a=[]
for i in range(m):
    pi,yi=map(int,input().split())
    a.append([i,pi,yi])
b=[]
c=[]
for i in range(n):
    b.append([])
    c.append([])
for i in range(m):
    x=a[i][0]
    y=a[i][2]
    b[a[i][1]-1].append([x,y])

for i in range(n):
    b[i].sort(key=itemgetter(1))
    l=len(b[i])
    for j in range(l):
        a[b[i][j][0]].append(j+1)
for i in range(m):
    xi=a[i][1]
    yi=a[i][3]
    print('{0:06d}{1:06d}'.format(xi,yi))

Submission status: Accepted

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

ans = sorted(ans, key=lambda x:x[0])
for _, n in ans:
    print(n)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
citydic={}
for i in range(m):
    p,y=map(int,input().split())
    add=[i,p,y]
    temp=citydic.get(p,[])
    temp.append(add)
    citydic[p]=temp

#print(citydic)
def make_id(p):
    dif=6-len(str(p))
    res="".join(["0" for i in range(dif)])
    return res+str(p)

ansdic={}
for key, v in citydic.items():
    l=sorted(v,key=lambda x: x[2])
    #print(l)
    for x, templ in enumerate(l,1):
        #makeid
        citynum,p,y=templ
        id1=make_id(p)+make_id(x)
        ansdic[citynum]=id1

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

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
piys = [[] for _ in range(N)]
for i in range(M):
    p, y = map(int, input().split())
    piys[p-1].append((y, i))

ans = [None]*M
for p, iys in enumerate(piys):
    iys.sort()
    for k, (y, i) in enumerate(iys):
        ans[i] = "%06d%06d" % (p+1, k+1)

for i in ans:
    print(i)

Submission status: Accepted

Solution code:
import bisect
n,m = map(int,input().split())
data = []
for i in range(m):
    data.append(list(map(int,input().split())))
r = sorted(data,key= lambda x:(x[0],x[1]))
o = [[] for _ in range(100001)]

for i in range(m):
    o[r[i][0]].append(r[i][1])

for i in range(m):
    print("0"*(6-len(str(data[i][0]))),end="")
    print(data[i][0],end="")
    num = bisect.bisect_left(o[data[i][0]],data[i][1])+1
    print("0"*(6-len(str(num))),end="")
    print(num)

Submission status: Accepted

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

for i in range(M):
    p,y=map(int,input().split())
    li[p-1].append(y)#p市の集合に追加
    P.append(p)
    Y.append(y)

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

for p,y in zip(P,Y):
    zenhan="0"*(6-len(str(p)))+str(p)
    x=bisect.bisect_left(li[p-1], y)+1
    kouhan="0"*(6-len(str(x)))+str(x)
    print(zenhan+kouhan)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
num=[]
ans=[""]*m
numcount=[1]*n
count=1
for i in range(m):
    p,y=map(int,input().split())
    num.append([p,y,i])
stry= lambda val: val[1]
num.sort(key=stry)
for i in range(m):
    p=str(num[i][0])
    y=str(numcount[int(num[i][0])-1])
    numcount[int(num[i][0])-1]+=1
    ans[num[i][2]]="0"*(6-len(p))+p+"0"*(6-len(y))+y
for i in range(m):
    print(ans[i])

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
l = []
s = ""
tmp = 1
for i in range(m):
  p,y = map(int,input().split())
  l.append([str(p).zfill(6),y,i+1])
  
l = sorted(l, key=lambda x:(x[0],x[1]))
#print(l)
for i in range(m):
  s = ""
  if i == 0 or l[i-1][0] != l[i][0]:
    tmp = 1
  else:
    tmp += 1
  s = l[i][0] + str(tmp).zfill(6)
  l[i].append(s)
    
l = sorted(l, key=lambda x:(x[2]))

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

Submission status: Accepted

Solution code:
#import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep='\n')

N, M = map(int, input().split())
# PY = [list(map(int, input().split())) for _ in range(M)]
PY = []
for i in range(M):
    P, Y = map(int, input().split())
    PY.append((i, P, Y))

PYs = sorted(PY, key=lambda x:(x[1], x[2]))
# print(PYs)

d = defaultdict(int)
ress = []
for py in PYs:
    i, p, y = py
    ress.append((i, p, d[p]+1))
    d[p] += 1

ress.sort(key=lambda x: x[0])
for res in ress:
    i, p, o = res
    print(str(p).zfill(6)+str(o).zfill(6))

Submission status: Accepted

Solution code:
import bisect
from collections import defaultdict

N, M = map(int, input().split(' '))
cities = []
years = defaultdict(list)
for _ in range(M):
    p, y = map(int, input().split(' '))
    cities.append((p, y))
    years[p].append(y)

for p in years.keys():
    years[p].sort()

for p, y in cities:
    print('{:06}{:06}'.format(p, bisect.bisect_right(years[p], y)))

Submission status: Accepted

Solution code:
from collections import Counter

N, M = map(int, input().split(' '))
records = [tuple(map(int, input().split(' '))) for _ in range(M)]
s_records = sorted(records)

counter = Counter()
d = {}

for p, y in s_records:
    counter[p] += 1
    d[(p, y)] = '{:06}{:06}'.format(p, counter[p])

for p, y in records:
    print(d[(p, y)])

Submission status: Accepted

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

for i in range(M):
  p, y = map(int, input().split())
  D[p-1].append((y, i)) #市ごとにリストに入れる．この時，元の順番をタプルの1番目の要素として入れておく

ans = [None]*M

for i, d in enumerate(D): #enumerateは要素の中身とインデックス番号を持ってこれる．print(i, d)で確認
  d.sort()
  for k, (y, j) in enumerate(d): #こちらも同様．(y, j)となっているため，yには年数が，jには元の順番の情報が入る
    ans[j] = str(i+1).zfill(6) + str(k+1).zfill(6) #ans[j]に12桁の認識番号を挿入

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

Submission status: Accepted

Solution code:
import sys
n,m = map(int, sys.stdin.readline().rstrip("\n").split())
city = {}
yton = {}
for i in range(m):
    p,y = map(int, sys.stdin.readline().rstrip("\n").split())
    if p not in city.keys():
        city[p] = []
        city[p].append(y)
        yton[y] = i
    else:
        city[p].append(y)
        yton[y] = i
ans = [None]*m
for p in city.keys():
    city[p].sort()
    for i,y in enumerate(city[p]):
        ans[yton[y]] = str(p*(10**6)+i+1).zfill(12)
print(*ans, sep = '\n')

Submission status: Accepted

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

l=[[] for j in range(n)]
for i in range(m):
  p,y=map(int,input().split())
  l[p-1].append([y,i])
for j in range(n):
  l[j].sort(key=lambda x:x[0])
lis=[]
for j in range(n):
  for t in range(len(l[j])):
    pre='0'*(6-len(str(j+1)))+str(j+1)
    y='0'*(6-len(str(t+1)))+str(t+1)
    b=pre+y
    lis.append([b,l[j][t][1]])
lis.sort(key=lambda x:x[1])
for li in lis:
  print(li[0])

Submission status: Accepted

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

ans=[0]*m
for i in range(n):
    sa=sorted(a[i],key=lambda x:x[0])
    order=1
    for tpl in sa:
        ans[tpl[1]]='0'*(6-len(str(i+1)))+str(i+1)+'0'*(6-len(str(order)))+str(order)
        order+=1
print(*ans,sep='\n')

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
def input(): return sys.stdin.readline().strip()


def main():
    N, M = map(int, input().split())
    pref = defaultdict(list)
    pref_list = [0] * (M + 1)
    for i in range(M):
        p, y = map(int, input().split())
        pref_list[i + 1] = p
        pref[p].append((y, i + 1))
    
    for p in pref: pref[p].sort()
    order = [0] * (M + 1)
    for p in pref:
        for x, (y, i) in enumerate(pref[p]):
            order[i] = x + 1
    
    for i in range(1, M + 1):
        p = pref_list[i]
        x = order[i]
        print("{p:06}{x:06}".format(p=p, x=x))





if __name__ == "__main__":
    main()

Submission status: Accepted

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

n, m = map(int, input().split())
pyi = []
for i in range(m):
    p,y= map(int, input().split())
    pyi.append([p,y,i]) #県番号、誕生年、市番号の順

pyi.sort(key=lambda x: x[1]) #誕生年でソート
pyi.sort(key=lambda x: x[0]) #県番号でソート
#県番号の順番で並びつつも、同県の中では誕生年順になっている

ken = 0 #県番号の初期化
for i in range(m):
    if pyi[i][0] != ken: #新しい県に突入した時
        ken = pyi[i][0] #県番号を更新
        x = 1 #xは同県内での順位を表す
    else: #前と同じ県の時
        x += 1 #同県内の順位は1つ手前の市+1
    pyi[i].append(x) #リストpyiの要素の各リストの末尾に同県内の順位を付け加える

pyi.sort(key=lambda x: x[2]) #出力順に直すために市番号でソート
for i in range(m): #県番号と同県内の順位をゼロ埋めして出力
    print(str(pyi[i][0]).zfill(6)+str(pyi[i][3]).zfill(6))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)

def main():
    n, m = map(int, input().split())
    h = {}
    pres = [1] * n
    cities = []
    year_pres = {}
    years = []
    for i in range(m):
        p, y = map(int, input().split())
        cities.append((p, y))
        year_pres[y] = p
        years.append(y)
    years.sort()
    for year in years:
        pre = year_pres[year]
        h[year] = pres[pre - 1]
        pres[pre - 1] += 1
    for city in cities:
        a = str(city[0]).zfill(6)
        b = str(h[city[1]]).zfill(6)
        print(a + b)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def resolve():
    n,m=map(int,input().split())
    py=[[0]*3 for _ in range(m)]
    for i in range(m):
        p,y=map(int,input().split())
        py[i][0],py[i][1],py[i][2]=p,y,i
    py.sort()
    ans=[[''] for _ in range(m)]
    cnt=[0]*(n+1)
    for p,y,i in py:
        cnt[p]+=1
        ans[i]='0'*(6-len(str(p)))+str(p)+'0'*(6-len(str(cnt[p])))+str(cnt[p])
    for i in ans:
        print(i)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

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

c = []
for x, p in enumerate(pre):
    p.sort(key = lambda x : x[1])

    for j, (i, y) in enumerate(p):
        c.append((i, x+1, j+1))

c.sort(key = lambda x :x[0])
for _, x, y in c:
    print(str(x).zfill(6)+str(y).zfill(6))

Submission status: Accepted

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

#(year, city)
prefs = [[] for _ in range(n + 1)]

#this list includes rel between city/pref
cities = []

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

for i in range(1, n + 1):
    prefs[i].sort()

table = {}

for i in range(1, n + 1):
    for j in range(len(prefs[i])):
        year, city = prefs[i][j]
        pref = i
        table[(pref, city)] = j + 1

for i in range(m):
    city = i + 1
    pref = cities[i]
    order = table[(pref, city)]

    pref = str(pref)
    order = str(order)
    ans = format(pref, '0>6') + format(order, '0>6')
    print(ans)

Submission status: Accepted

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

rank_map={}
rank=0
p=None

for t in sorted(data):
    if p!=t[0]:
        p=t[0]
        rank=1
    rank_map[t]='%06d%06d' % (t[0], rank)
    rank+=1

for t in data:
    print(rank_map[t])

Submission status: Accepted

Solution code:
n,m = list(map(int, input().split()))
#data={}
#l=[]
data = [tuple(map(int, input().split())) for _ in range(m)]
#for i in range(m):
#    tup = tuple(map(int, input().split()))
#    data[i]=tup
#    l.append(tup)

m={}
n=0
p=None
for t in sorted(data):
#    print('p=',p,'t[0]=',t[0])
    if p!=t[0]:
        p=t[0]
        n=1
    m[t]='%06d%06d' % (t[0], n)
    n+=1
#print(m)
for k in data:
    print(m[k])

Submission status: Accepted

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

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

ID=[0 for _ in range(M)]
for j in range(N):
    Pre[j].sort()
    for k in range(len(Pre[j])):
        ID[Pre[j][k][1]-1]=str(j+1).zfill(6)+str(k+1).zfill(6)

for d in ID:
    print(d)

Submission status: Accepted

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


def solve(N: int, M: int, P: "List[int]", Y: "List[int]"):
    from itertools import count
    from collections import defaultdict
    Q = sorted(zip(Y, P, count(0)))
    c = defaultdict(int)
    ans = [None] * M
    for y, p, i in Q:
        c[p] += 1
        ans[i] = str(p).zfill(6) + str(c[p]).zfill(6)
    return ans


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    P = [int()] * (M)  # type: "List[int]"
    Y = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        P[i] = int(next(tokens))
        Y[i] = int(next(tokens))
    print(*solve(N, M, P, Y), sep='\n')

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

Submission status: Accepted

Solution code:
def c_id():
    from collections import defaultdict
    N, M = [int(i) for i in input().split()]
    Cities = [[int(i) for i in input().split()] for j in range(M)]

    dic = defaultdict(list)
    # 県毎に市をまとめる
    for p, y in Cities:
        dic[p].append(y)
    # 市の認識番号を (座標) 圧縮
    for p, lst in dic.items():
        dic[p] = {v: k for k, v in enumerate(sorted(lst), 1)}
    return '\n'.join(['{0:06d}{1:06d}'.format(p, dic[p][y]) for p, y in Cities])

print(c_id())

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
temp=[0]*m
tempn=[]
for i in range(0,m):
  p,y=map(int,input().split())
  temp[i]=[i,p,y]
  tempn.append(p)
temp.sort(key=lambda x: x[2])  
temp.sort(key=lambda x: x[1])  
j=1
tempn=list(set(tempn))
tempn.sort()
k=0
n=tempn[k]
for i in range(0,m):
  if temp[i][1]==n:
    tempa=str(n)
    tempj=str(j)
    temp[i][1]=tempa.zfill(6)
    temp[i][2]=tempj.zfill(6)
    j=j+1
  else:
    k=k+1
    if k>=len(tempn):
      break
    n=tempn[k]
    j=1
    tempa=str(n)
    tempj=str(j)
    temp[i][1]=tempa.zfill(6)
    temp[i][2]=tempj.zfill(6)
    j=j+1
temp.sort(key=lambda x: x[0])
for i in range(0,m):
  print(temp[i][1]+temp[i][2])

Submission status: Accepted

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

for p in range(1,n+1):
    tmp=sorted(x[p])
    for j in range(len(tmp)):
        ans[tmp[j][1]]=str(p).zfill(6)+str(j+1).zfill(6)

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

Submission status: Accepted

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

for p in range(1,n+1):
    x[p].sort()
    for j in range(len(x[p])):
        ans[x[p][j][1]]=str(p).zfill(6)+str(j+1).zfill(6)

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

Submission status: Accepted

Solution code:
_,m=map(int,input().split())
ta=[list(map(int,input().split()))+[i] for i in range(m)]
a=sorted(ta)
ans=[-1]*m
j=0
for i in range(m):
    if j!=a[i][0]:
        j=a[i][0]
        k=1
    p=str(a[i][0]).zfill(6)+str(k).zfill(6)
    ans[a[i][2]]=p
    k+=1

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

Submission status: Accepted

Solution code:
N,M=list(map(int,input().split()))
import sys
l=[list(map(int,_.rstrip().split())) for _ in sys.stdin.readlines()]
n=sorted(l,key=lambda x:x[1])
dic={}
mem=[0]*N
for i,j in n:
   mem[i-1]+=1
   dic[i,j]=str(i).zfill(6)+str(mem[i-1]).zfill(6)
for i,j in l:
   print(dic[i,j])

Submission status: Accepted

Solution code:
# ABC113C
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


from collections import defaultdict
n,m = map(int, input().split())
p = defaultdict(list)
ps = [None] * m
ys = [None] * m
for i in range(m):
    pp,yy = map(int, input().split())
    p[pp].append((i,yy))
    ps[i] = pp
    ys[i] = yy
d = {}
for k,v in p.items():
    tmp = sorted(v, key=lambda x: x[1])
    d[k] = {j:i+1 for i,(j,y) in enumerate(tmp)}

for i in range(m):
    print(str(ps[i]).rjust(6,"0")+str(d[ps[i]][i]).rjust(6, "0"))

Submission status: Accepted

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

py.sort()

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

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

for pypy in py:
    ans = str(pypy[0]).zfill(6) + str(pypy[3]).zfill(6)
    print(ans)

Submission status: Accepted

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

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

last_P = -1
counter = 1
for P, Y in sorted(PYs):
    if last_P == P:
        counter += 1
    else:
        last_P = P
        counter = 1
    d[(P, Y)] = "{0:0>6}{1:0>6}".format(P, counter)
    
for t in PYs:
    print(d[t])

Submission status: Accepted

Solution code:
DEBUG = False

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

if DEBUG:
    print(iPY)

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

if DEBUG:
    print(sorted_iPY)

counts = {}

for n, ipy in enumerate(sorted_iPY):
    i, p, y = ipy
    if p not in counts:
        counts[p] = 1
    else:
        counts[p] += 1
    if DEBUG:
        print(counts)
    sorted_iPY[n].append("{:0=6}".format(p) +  "{:0=6}".format(counts[p]))

if DEBUG:
    print(sorted_iPY)

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

if DEBUG:
    print(restored_iPY)

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

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline

def flatten_2dim(array):
    return [item for sublist in array for item in sublist]

def main():
    N, M = map(int, readline().split())
    number = [[] for _ in range(N)]
    for i in range(M):
        p, y = map(int, readline().split())
        p -= 1
        number[p].append([p+1, y, i])
    for pnumber in number:
        if len(pnumber)==0:
            continue
        pnumber.sort(key=lambda x: x[1])
        pbase = str(pnumber[0][0])
        numleft = '0'*(6-len(pbase)) + pbase
        cnt = 1
        for tmp in pnumber:
            numbase = str(cnt)
            numright = '0'*(6-len(numbase)) + numbase
            base = numleft+numright
            tmp.append(base)
            cnt += 1
    fnumber = flatten_2dim(number)
    fnumber.sort(key=lambda x: x[2])

    for tmp in fnumber:
        print(tmp[3])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# C - IDC

import bisect
import sys
readline = sys.stdin.readline

base = 1000000000000
N, M = map(int, readline().split())
PY = []
T = [[] for _ in range(N+1)]

for i in range(M):
    P, Y = map(int, readline().split())
    PY.append((P, Y))

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

for i in range(M):
    T[PY_sorted[i][0]].append(PY_sorted[i][1])

for i in range(M):
    n = bisect.bisect_right(T[PY[i][0]], PY[i][1])
    print(str(base + PY[i][0]*1000000 + n)[1:])

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
cnt = [[] for _ in range(n)]
for i in range(m):
    p, y = map(int, input().split())
    cnt[p-1].append((y, i))
ans = [None]*m
for p, li in enumerate(cnt):
    if not li:
        continue
    li.sort()
    for j, (y, i) in enumerate(li):
        ans[i] = '{:06d}{:06d}'.format(p+1, j+1)
print('\n'.join(ans))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
PYi = [list(map(int, input().split()))+[i] for i in range(M)]
PYi.sort()
ans = ['']*M
counter = {}

for v in PYi:
    P, Y, i = v

    if not P in counter:
        counter[P] = 1
    else:
        counter[P] += 1

    tmp = ''
    tmp += str(P).zfill(6)
    tmp += str(counter[P]).zfill(6)
    ans[i] = tmp

for v in ans:
    print(v)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
import bisect
from collections import deque
from fractions import gcd
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def Yes(): print("Yes"); return
def No(): print("No"); return

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

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

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#############
# Main Code #
#############

N,M = inputIL()
data = []
for i in range(M):
  data.append([i] + inputIL())

dic = {p:[] for p in range(N)}

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

ans = []
for p in dic:
  dic[p].sort()
  for k in range(len(dic[p])):
    y,i = dic[p][k]
    ans.append((i,(p+1)*1000000+k+1))
    
ans.sort()   
for i,id in ans:
  print("{:012}".format(id))