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:
#!/usr/bin/env python3
import sys

dic = {}

def list_sort(x):
    values = dic[x]
    values.sort()

    return {x: values}

def solve(N: int, M: int, P: "List[int]", Y: "List[int]"):
    for i in range(N):
        dic[i + 1] = []
    
    for i in range(M):
        dic[P[i]].append(Y[i])

    sorted_dic = {}
    for key in dic.keys():
        tmp = {}
        values = dic[key]

        values.sort()
        for i in range(len(values)):
            tmp[values[i]] = i + 1

        sorted_dic[key] = tmp


    for m in range(M):
        key = P[m]
        value = Y[m]
        sorted_ranked_dic = sorted_dic[key]
        rank = sorted_ranked_dic[value]

        print('{0:06d}'.format(key, rank) + '{0:06d}'.format(rank))



    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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))
    solve(N, M, P, Y)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
ppyy = [list(map(int, input().split())) for _ in range(m)]
order = [{}] * (n + 1)
cnt = [1] * (n + 1)
for p, y in sorted(ppyy, key=lambda x: x[1]):
    order[p].update({y: cnt[p]})
    cnt[p] += 1
for p, y in ppyy:
    cnt[p] += 1
    print(str(format(p, '06')) + str(format(order[p][y], '06')))

Submission status: Accepted

Solution code:
n, m = [int(x) for x in input().split()]

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

ans_list = [""] * m
for p in range(1, n + 1):
    temp_list[p].sort()
    for j in range(len(temp_list[p])):
        _, i = temp_list[p][j]
        ans_list[i] = "{:06}{:06}".format(p, j + 1)

for ans in ans_list:
    print(ans)

Submission status: Accepted

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

def main():
    N, M = map(int, input().split())
    P = [None] * M
    Y = [None] * M
    ans = [set() for _ in range(N)]
    for i in range(M):
        p, y = map(int, input().split())
        P[i], Y[i] = p, y
        ans[p-1].add(y)
    ans = [sorted(a) for a in ans]
    
    for i in range(M):
        k = P[i]
        j = bisect_right(ans[k-1],Y[i])
        print(str(k).zfill(6)[-6:] + str(j).zfill(6)[-6:])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
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[0], x[1]))


P = 0
c = 1
ans = []
for p, y, i in PYI:
    if p != P:
        c = 1
        P = p
    else:
        c += 1
    ans.append([i, '{:06d}{:06d}'.format(p, c)])

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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
ipyth = [[i] * 4 for i in range(m)]
for i in range(m):
    ipyth[i][1], ipyth[i][2] = map(int, input().split())
ipyth.sort(key=lambda x:(x[1], x[2]))
for i in range(m):
    if i:
        if ipyth[i][1] == ipyth[i - 1][1]:
            ipyth[i][3] = ipyth[i - 1][3] + 1
        else:
            ipyth[i][3] = 1
    else:
        ipyth[i][3] = 1
ipyth.sort(key = lambda x: x[0])
for i in range(m):
    print(str(ipyth[i][1]).zfill(6) + str(ipyth[i][3]).zfill(6))

Submission status: Accepted

Solution code:
from collections import defaultdict

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

# 3つめの要素でsort からの 2つめの要素でsort
l_sorted = sorted((y,p,i) for i,(p,y) in enumerate(l))

d = defaultdict(lambda: 0)

ans = [None] * M

for a,b,c in l_sorted:
    d[b] += 1
    ans[c] = str(b).zfill(6) + str(d[b]).zfill(6)
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
t = []
for i in range(m):
    p, y = map(int,input().split())
    t.append([i,p,y,0])
t.sort(key=lambda x:x[2])                 # yでソート
t.sort(key=lambda x:x[1])                 # pでソート
city = t[0][1]
city_num = 0
for i in range(m):                       # pでソート済みなのでこう書ける              
    if t[i][1] == city:
        city_num += 1
        t[i][3] += city_num
    else:
        city = t[i][1]
        t[i][3] = 1
        city_num = 1
t.sort()                                 # t.sort(key=lambda x:x[0])と同じ
for i in t:
    ans = "%06d" % i[1] + "%06d" % i[3]
    print(ans)

Submission status: Accepted

Solution code:
n, m = map(int,input().split())
li = []
ans = []
#市, 年, 出力順で格納

for i in range(m):
    x = list(map(int,input().split()))
    x.append(i)
    li.append(x)

li.sort()

for i in range(len(li)):
    if i == 0:
        y = 1
    elif li[i][0] == li[i-1][0]:
        y += 1
    else:
        y = 1
    li[i].append(str(li[i][0]).rjust(6,'0') + str(y).rjust(6,'0'))

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

for i in li:
    print(i[3])

Submission status: Accepted

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

for i in range(M):
    pi, yi = map(int, input().split())
    records.append([i, pi, yi, "X"])

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

# for i in records:
#     print(i)
city = records[0][1]
city_num = 0

for i in range(M):
    if records[i][1] == city:
        city_num += 1
        records[i][3] = city_num
    else:
        city = records[i][1]
        records[i][3] = 1
        city_num = 1
records.sort()
for record in records:
    ans = "%06d" % record[1] + "%06d" % record[3]
    print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

n, m = map(int, input().split())
PY = [tuple(map(int, input().split())) for _ in range(m)]
ypi = sorted((y, p, i) for i, (p, y) in enumerate(PY))
d = defaultdict(lambda: 0)

ans = [None]*m

for y, p, i in ypi:
    d[p] += 1
    ans[i] = str(p).zfill(6) + str(d[p]).zfill(6)

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

Submission status: Accepted

Solution code:
n, m = map(int,input().split())
ypi = []
for i in range(m):
    p, y = map(int,input().split())
    p = str(p)
    p = '0'*(6-len(p)) + p
    ypi.append((y, p, i))
ypi.sort()

p_dict = {}
for y, p, i in ypi:
    p_dict[p] = []

for y, p, i in ypi:
    p_dict[p].append(i)

ans_l = [0]*m
for p, i_l in p_dict.items():
    for j, i in enumerate(i_l):
        j = str(j+1)
        j = '0'*(6-len(j)) + j
        ans_l[i] = p + j

for val in ans_l:
    print(val)

Submission status: Accepted

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

py=[]
#初期値が0の辞書

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

for _ in range(m):
    p,y=map(int,input().split())
    py.append((p,y))
    p2year[p].append(y)

#初期値が0の辞書
from collections import defaultdict
py2index = defaultdict(lambda: 0) 

for item in range(n+1):
    p2year[item].sort()
    for index,temp in enumerate(p2year[item]):
        py2index[(item,temp)]=index+1

for item in py:
    pp=item[0]
    yy=item[1]
    result=str(pp).zfill(6)+str((py2index[(pp,yy)])).zfill(6)
    print(result)

Submission status: Accepted

Solution code:
N,M = map(int,input().split()) 
Pref_info = [[] for _ in range(N)] 
for i in range(M):
    P,Y = map(int,input().split())
    Pref_info[P - 1].append([Y,i])
ans = [""]* M 
for i in range(N): 
    Pref_info[i].sort()
    for index, p in enumerate(Pref_info[i]):
        ans[p[1]] = "{0}{1}".format(str(i+1).zfill(6),str(index+1).zfill(6))
for i in ans:
    print(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:
N,M = map(int,input().split())
PY = [tuple(map(int,input().split())) for i in range(M)]

#こういう書き方ができると暗記する
ypi = sorted((y,p,i) for i,(p,y) in enumerate(PY))
 
from collections import defaultdict
d = defaultdict(lambda: 0)

#list初期化
ans = [None] * M

for y,p,i in ypi:
    d[p] += 1

    #lenがMのansのlistに添字ではなくて、意図的に、iでインデックス指定で入れる。
    #こうすることで、わざわざ探す処理なく、順番も入れ替えることなく処理が可能
    ans[i] = str(p).zfill(6) + str(d[p]).zfill(6)
print(*ans, sep='\n')

Submission status: Accepted

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

newP=[]
for p in P:
    p=sorted(p)
    newP.append(p)

for i in range(M):
    t=L[i]
    p,y=t
    num=bisect.bisect_right(newP[p-1],y)
    
    p=str(p).zfill(6)
    num=str(num).zfill(6)
    print(p+num)

Submission status: Accepted

Solution code:
def main():
    from operator import itemgetter
    import sys
    input = sys.stdin.readline
    N, M = map(int, input().split())

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

    ans = [''] * M
    for p, pref in enumerate(prefectures, start=0):
        pref.sort(key=itemgetter(0))
        for i, (_, m) in enumerate(pref, start=1):
            ans[m] = '{:06d}{:06d}'.format(p, i)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
import sys
try:
    from typing import List
except ImportError:
    pass


def solve(N: int, M: int, P: "List[int]", Y: "List[int]"):
    cities = sorted(
        (Yi, Pi, i)
        for i, (Pi, Yi) in enumerate(zip(P, Y))
    )
    ans = [""] * M
    cnt = defaultdict(int)
    for Yi, Pi, i in cities:
        cnt[Pi] += 1
        ans[i] = "%06d%06d" % (Pi, cnt[Pi])

    for ansi in ans:
        print(ansi)


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))
    solve(N, M, P, Y)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6) #再帰関数の上限
import math
from copy import copy, deepcopy
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque 
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする

def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds

def main():
    mod = 10**9+7
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    #N = int(input())
    N, M = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    tot=[[] for _ in range(N+1)]
    ys=[0]*M
    for i in range(N):
        heapify(tot[i])
    for i in range(M):
        P, Y = map(int, input().split())
        heappush(tot[P],[Y,i])
        ys[i]=Y
    tset=[]
    ans=['']*M
    for i in range(N+1):
        t1=tot[i]
        if len(t1)<1:continue
        p=str(i).zfill(6)
        j=0
        while len(t1):
            t, i1=heappop(t1)
            tx=str(j+1).zfill(6)
            ans[i1]=''.join((p,tx))
            j+=1
    print('\n'.join(ans))





if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6) #再帰関数の上限
import math
from copy import copy, deepcopy
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque 
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする

def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds

def main():
    mod = 10**9+7
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    #N = int(input())
    N, M = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    tot=[[] for _ in range(N+1)]
    ys=[0]*M
    for i in range(N):
        heapify(tot[i])
    for i in range(M):
        P, Y = map(int, input().split())
        heappush(tot[P],[Y,i])
        ys[i]=Y
    tset=[]
    ans=['']*M
    for i in range(N+1):
        t1=tot[i]
        if len(t1)<1:continue
        p=str(i).zfill(6)
        j=0
        while len(t1):
            t, i1=heappop(t1)
            tx=str(j+1).zfill(6)
            ans[i1]=p+tx
            j+=1
    print('\n'.join(ans))





if __name__ == "__main__":
    main()

Submission status: Accepted

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

import heapq
N,M = (int(x) for x in input().split())
pref = [[] for _ in range(N)]
ans = [0] * M
prefnumber = 0
for i in range(M):
    P,Y = (int(x) for x in input().split())
    pref[P-1].append((Y,i))
for p in pref:
    prefnumber += 1
    count = 1
    if p:
        heapq.heapify(p)
        while p:
            temp = heapq.heappop(p)
            ans[temp[1]] = ''.join([str(prefnumber).zfill(6),str(count).zfill(6)])
            count += 1
print('\n'.join(ans))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
prefectures = [[] for _ in range(10 ** 5)]

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

ans = [''] * m
for p in range(10 ** 5):
    prefecture = prefectures[p]
    prefecture.sort(key=lambda x: x[0])
    for i in range(len(prefecture)):
        ans[prefecture[i][1]] = '{:006}{:006}'.format(p + 1, i + 1)

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

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
py=[]
ans=[0]*m
for j in range(m):
    py.append(list(map(int,input().split()))+[j])
py.sort(key=lambda x:x[1])
p=[0]*n
for i in range(m):
  p[py[i][0]-1]+=1
  ans[py[i][2]]='0'*(6-len(str(py[i][0])))+str(py[i][0])+'0'*(6-len(str(p[py[i][0]-1])))+str(p[py[i][0]-1])
for k in range(m):
    print(ans[k])

Submission status: Accepted

Solution code:
from collections import defaultdict

N, M = map(int, input().split())
PY = defaultdict(dict)
for i in range(M):
    temp = list(map(int, input().split()))
    PY[temp[0]][temp[1]] = i
PY_sort = sorted(PY.items(), key=lambda x: x[0])

city = {}
for n, ms in PY_sort:
    ms_sort = sorted(ms.items(), key=lambda x: x[0])
    k = 1
    for m, i in ms_sort:
        city[i] = "".join([str(n).zfill(6), str(k).zfill(6)])
        k += 1
city_sort = sorted(city.items(), key=lambda x: x[0])
for i in range(M):
    print(city_sort[i][1])

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
C = [[] for k in range(N)]
for k in range(M):
    P, Y = map(int,input().split())
    C[P-1].append([Y,k])
D = []
for e in C:
    D.append(sorted(e))
A = [0]*M
for k in range(N):
    c = 1
    for e in D[k]:
        A[e[1]] = (k+1)*1000000 + c
        c += 1
for e in A:
    print(str(e).zfill(12))

Submission status: Accepted

Solution code:
import bisect
from collections import defaultdict
n,m = map(int,input().split())
p = [list(map(int, input().split())) for _ in range(m)]
 
a = defaultdict(list)
for x,y in sorted(p):
    a[x].append(y)
for x,y in p:
    
    z=bisect.bisect(a[x],y)
    print("{0:06d}{1:06d}".format(x,z))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
PY = [tuple(list(map(int, input().split()))+[i]) for i in range(M)]
PY.sort(key=lambda x: x[1])
ans = ['']*M
P = [0]*N
for p, y, i in PY:
    ret = ''
    p -= 1
    P[p] += 1
    ret += '{:0=6}'.format(p+1)
    ret += '{:0=6}'.format(P[p])
    ans[i] = ret
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from bisect import bisect_left

n, m = map(int, readline().split())
py = [list(map(int, readline().split())) for _ in range(m)]
check = sorted(py)
idx = [0] * (n + 1)
memo = 0
for i, (p, _) in enumerate(check):
    if memo != p:
        idx[p] = i
        memo = p
for p, y in py:
    yy = str(bisect_left(check, [p, y]) - idx[p] + 1)
    p = str(p)
    print('0' * (6 - len(p)) + p + '0' * (6 - len(yy)) + yy)

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

pnow = pyi[0][0]
cnt = 1

ans = [-1 for _ in range(m)]

for p,y,i in pyi:
  if pnow != p:
    cnt = 1
    pnow = p
  ans[i] = str(p).zfill(6) + str(cnt).zfill(6)
  cnt += 1
print("\n".join(ans))

Submission status: Accepted

Solution code:
import bisect

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

data = [[] for _ in range(n)]
query = []

for i in range(m):
    array = list(map(int, input().split()))
    query.append(array)
    a = array[0] - 1
    b = array[1]
    data[a].append(b)

cnt = 0
for i in data:
    i.sort()
    data[cnt] = i
    cnt += 1
    
for i, j in query:
    num = bisect.bisect_left(data[i-1], j) + 1
    x = str(i).zfill(6)
    y = str(num).zfill(6)
    z = str(x) + str(y)
    print(z)

Submission status: Accepted

Solution code:
from bisect import bisect_left
N,M = map(int,input().split())
C = {i:[] for i in range(1,N+1)}
city = [0 for _ in range(M+1)]
for j in range(1,M+1):
    p,y = map(int,input().split())
    C[p].append((y,j))
    city[j]=(p,y)
for p in C:
    if len(C[p])>0:
        C[p] = sorted(C[p],key=lambda x:x[0])
for j in range(1,M+1):
    p,y = city[j]
    ind = bisect_left(C[p],(y,j))
    p = str(p)
    if len(p)<6:
        p ="0"*(6-len(p))+p
    x = str(ind+1)
    if len(x)<6:
        x = "0"*(6-len(x))+x
    print(p+x)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


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


def read_a_int():
    return int(read())


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H):
    '''
    H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_matrix(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right

# https://atcoder.jp/contests/abc113/tasks/abc113_c
N, M = read_ints()
cnts = [0] * N
YPI = []
for i in range(M):
    p, y = read_ints()
    YPI.append((y, p - 1, i))

YPI.sort()  # 年の昇順に
IDs = []
for y, p, i in YPI:
    cnts[p] += 1
    x = str(cnts[p])
    p = str(p + 1)

    IDs.append((i, p.zfill(6) + x.zfill(6)))

IDs.sort()
for i, iid in IDs:
    print(iid)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

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

ans = [''] * M
for p, grp in A.items():
    for j, (_, i) in enumerate(sorted(grp), start=1):
        ans[i] = '%06d%06d' % (p, j)
print(*ans, sep='\n')

Submission status: Accepted

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

for ls in Ps:
    ls.sort()

for p, y in PY:
    pid = "{:06}".format(p)
    cid = "{:06}".format(bisect.bisect_right(Ps[p-1], y))
    print(pid+cid)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, m = map(int, input().split())
    PY = []
    for i in range(m):
        p, y = map(int, input().split())
        PY.append([i, p, y])
    PY = sorted(PY, key=lambda x: x[2])
    PY = sorted(PY, key=lambda x: x[1])

    res = [] * m
    prev = PY[0][1]
    last = 0
    for i in range(m):
        idx, p, y = PY[i]
        if prev != p:
            last = 1
            prev = p
        else:
            last += 1

        id = str(p).zfill(6) + str(last).zfill(6)
        res.append([idx, id])

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


if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

n,m = inpl()
d = dict()
z = []
res = [None] * m
for i in range(m):
    a,b = inpl()
    d[(a,b)] = i
    z.append([a,b])
z.sort(key=lambda x:x[1])
z.sort(key=lambda x:x[0])
# print(z)
cnt = 0
now = z[0][0]
for i,t in enumerate(z):
    ind = d[(t[0],t[1])]
    if now == t[0]:
        cnt += 1
        res[ind] = [now,cnt]
    else:
        cnt = 1
        now = t[0]
        res[ind] = [now,cnt]

for a,b in res:
    print(str(a).zfill(6) + str(b).zfill(6))

Submission status: Accepted

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

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

lst = [list(map(int, input().split())) + [i] for i in range(M)]
# print (lst)

lst.sort(key = lambda x: x[1]) #x番目が小さい順に並べる
lst.sort(key = lambda x: x[0])


ans = [0] * M

count = 0
tmp = 0 #１つ前の県の番号
for p, y, i in lst:
    if tmp == p:
        count += 1
    else:
        count = 1
        tmp = p
    tmp_ans = str(p).zfill(6) + str(count).zfill(6)
    ans[i] = tmp_ans

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

Submission status: Accepted

Solution code:
from operator import itemgetter


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

info = sorted(info, key=itemgetter(1))
ans = [0] * m

cnt_ind = [1] * (n + 1)
for i in range(m):
    p, y, ind = info[i]
    cnt = cnt_ind[p]
    cnt_ind[p] += 1
    ans[ind] = ("0000000"+str(p))[-6:] + ("0000000"+str(cnt))[-6:]
for i in ans:
    print(i)

Submission status: Accepted

Solution code:
n,m =map(int,input().split())
lis = [list(map(int,input().split())) for i in range(m)]
for i in range(m):
    lis[i].append(i)
lis.sort()
cnt = 1
ans = []
ans.append([lis[0][-1],format(lis[0][0]).zfill(6)+format(1).zfill(6)])
for i in range(m-1):
    if lis[i][0] == lis[i+1][0]:
        cnt += 1
        ans.append([lis[i+1][-1],format(lis[i+1][0]).zfill(6)+format(cnt).zfill(6)])
    else:
        cnt = 1
        ans.append([lis[i+1][-1],format(lis[i+1][0]).zfill(6)+format(cnt).zfill(6)])
ans.sort(key = lambda x:x[0])
for i,x in ans:
    print(x)

Submission status: Accepted

Solution code:
def main():
    n, m = map(int, input().split())
    group = {i: [] for i in range(1, n + 1)}
    for i in range(m):
        p, y = map(int, input().split())
        group[p].append([y, i])
    answer = ["" for _ in range(m)]
    for i in range(1, n + 1):
        group[i].sort(key=lambda x: x[0])
    for i in range(1, n + 1):
        for j, yi in enumerate(group[i]):
            y, k = yi
            answer[k] = str(i).zfill(6) + str(j + 1).zfill(6)
    print("\n".join(answer))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
def solve(N,M):
    pref = [[] for _ in range(N)]
    P = [0]*M
    Y = [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()
    ans = []
    for i in range(M):
        ind = bisect_left(pref[P[i]-1],Y[i])
        ans.append('0'*(6-len(str(P[i])))+str(P[i])+'0'*(6-len(str(ind+1)))+str(ind+1))
    return ans
print(*solve(N,M),sep='\n')

Submission status: Accepted

Solution code:
N,M=map(int, input().split())
PY=[tuple(map(int, input().split()))for _ in range(M)]
ans=[None]*M
I=sorted(range(M),key=lambda i: PY[i][1])
C=[0]*(N+1)
for i in I:
    p=PY[i][0]
    C[p]+=1
    ans[i]=(p,C[p])
def f(x):
    s=str(x)
    return "0"*(6-len(s))+s
for p,c in ans:
    print(f(p)+f(c))

Submission status: Accepted

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

from collections import defaultdict
d = defaultdict(lambda: 0)
ans = [None] * M
for y,p,i in ypi:
    d[p] += 1
    ans[i] = str(p).zfill(6) + str(d[p]).zfill(6)
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
from bisect import bisect_right
dic = [[] for i in range(N)]

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

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

for j in range(M):
    p, y = shi[j]
    print('{:06}{:06}'.format(p, bisect_right(dic[p-1], y)))

Submission status: Accepted

Solution code:
f=lambda:map(int,input().split())
_,m=f()
d,t,c={},0,0
for p,y,i in sorted(list(f())+[i] for i in range(m)):
  if p>t: t,c=p,1
  else: c+=1
  d[i]=str(p).zfill(6)+str(c).zfill(6)
for _,v in sorted(d.items()): print(v)

Submission status: Accepted

Solution code:
import sys
f=lambda:map(int,sys.stdin.readline().split())
_,m=f()
d,t,c={},0,0
for p,y,i in sorted(list(f())+[i] for i in range(m)):
  if p>t: t,c=p,1
  else: c+=1
  d[i]=str(p).zfill(6)+str(c).zfill(6)
for _,v in sorted(d.items()): print(v)

Submission status: Accepted

Solution code:
import sys
f=lambda:map(int,sys.stdin.readline().split())
n,m=f()
lt=[]
for i in range(m):
  p,y=f()
  lt+=[(p,y,i)]
lt.sort()
d={}
t=c=0
for p,y,i in lt:
  if p>t: t,c=p,1
  else: c+=1
  d[i]=str(p).zfill(6)+str(c).zfill(6)
for _,v in sorted(d.items()): print(v)

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
Cities = []
for _ in range(M):
    Cities.append(list(map(int,input().split())))
L = [[] for i in range(N+1)]
for P, Y in Cities:
    L[P].append(Y)
for i in range(N+1):
    L[i].sort()
D = [{} for _ in range(N+1)]
for i in range(1, N+1):
    for val, key in enumerate(L[i], 1):
        D[i][key] = val

for P, Y in Cities:
    left = str(P).zfill(6)
    right = str(D[P][Y]).zfill(6)
    print(left + right)