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: Time Limit Exceeded

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

x = {i+1: [] for i in range(N)}
y = [None] * M
for i in range(M):
    P, Y = map(int, input().split())
    x[P].append(Y)
    y[i] = (P, Y)

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

for i in range(M):
    P, Y = y[i]
    print('{}{}'.format(str(P).zfill(6), str(x[P].index(Y) + 1).zfill(6)))

Submission status: Time Limit Exceeded

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

citys = []
c_append = citys.append
prefs = []
p_append = prefs.append
for i in range(M):
    P, Y = map(int, input().split())
    if P not in prefs:
        p_append(P)

    c_append(
        {
            "birth": Y,
            "pref": P,
            "number": "0" * (6 - len(str(P))) + str(P)
        }
    )

# check
for p in prefs:
    target_citys = [
        c
        for c in citys
        if c["pref"] == p
    ]
    target_citys.sort(key=lambda x: x["birth"])
    lot_num = 1
    for c in target_citys:
        c["number"] += "0" * (6 - len(str(lot_num))) + str(lot_num)
        lot_num += 1

for c in citys:
    print(c["number"])

Submission status: Time Limit Exceeded

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

PY2 = PY.copy()
PY2.sort(key=lambda x:(x[0],x[1]))
PY2
city = PY[0][0]
for p in PY:
    P_tmp = [i for i in PY2 if i[0]==p[0]]
    print(str(p[0]).zfill(6)+str(P_tmp.index(p)+1).zfill(6))

Submission status: Time Limit Exceeded

Solution code:
n, m =  map(int, input().split())
py = [map(int, input().split()) for _ in range(m)]
p, y = [list(i) for i in zip(*py)]
pre = {}
for i in range(m):
    if p[i] not in pre.keys():
        pre[p[i]] = []
    pre[p[i]].append(y[i])
for i in pre.keys():
    pre[i].sort()
for i in range(m):
    num = str(p[i]*(10**6)+(pre[p[i]].index(y[i])+1)).zfill(12)
    print(num)

Submission status: Time Limit Exceeded

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

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

for i in ken:
    if i != []:
        i.sort()

for p,y in pairs:
    x = ken[p-1].index(y) + 1
    print('{:0=6}{:0=6}'.format(p,x))

Submission status: Time Limit Exceeded

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

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

for i in d.keys():
    d[i] = sorted(d[i])

for pairs_ele in pairs:
    p = pairs_ele[0]
    y = pairs_ele[1]
    x = d[p].index(y) + 1
    print('{:0=6}{:0=6}'.format(p,x))

Submission status: Time Limit Exceeded

Solution code:
# C - IDC
import bisect
import sys
readline = sys.stdin.readline
 
base = 1000000000000
N, M = map(int, readline().split())
P = [0] * M
Y = [0] * M
T = [[] for _ in range(N+1)]
 
for i in range(M):
    P[i], Y[i] = map(int, readline().split())
    T[P[i]].append(Y[i])

for i in range(M):    
    T[P[i]].sort()
    
for i in range(M):
    num = bisect.bisect_right(T[P[i]], Y[i])
    print(str(base + P[i]*1000000 + num)[1:])

Submission status: Time Limit Exceeded

Solution code:
# C - IDC
import bisect
import sys
readline = sys.stdin.readline

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

for i in range(M):
    P[i], Y[i] = map(int, readline().split())
    T[P[i]].append(Y[i])
    T[P[i]].sort()

for i in range(M):
    num = bisect.bisect_right(T[P[i]], Y[i])
    print(str(base + P[i]*1000000 + num)[1:])

Submission status: Time Limit Exceeded

Solution code:
# C - IDC
import bisect

base = 1000000000000
N, M = map(int, input().split())
P = [0] * M
Y = [0] * M
T = [[] for _ in range(N+1)]

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

for i in range(M):
    num = bisect.bisect_right(T[P[i]], Y[i])
    print(str(base + P[i]*1000000 + num)[1:])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
n, m = map(int, input().split())
li = []
dic = defaultdict(list)
for i in range(m):
    p, y = map(int, input().split())
    li.append([p, y])
    dic[p].append(y)
for d in dic:
    dic[d].sort()
for p, y in li:
    ans1 = str(p).zfill(6)
    ans2 = str(dic[p].index(y) + 1).zfill(6)
    print(ans1+ans2)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
py_list = [list(map(int,input().split())) for nesya in range(m)]
py_sort = sorted(py_list,key=lambda x: x[1])
ho = [0]*(n+1)
for py1 in py_sort:
  ho[py1[0]] += 1
  py1.append(ho[py1[0]])
for py in py_list:
  for i in range(m):
    if py[1] == py_sort[i][1]:
      print(str(py[0]).zfill(6)+str(py_sort[i][2]).zfill(6))
      break

Submission status: Time Limit Exceeded

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

P, Y = [], []
dic = {}
for _ in range(M):
    p, y = map(int, input().split())
    P.append(p)
    Y.append(y)
    if p in dic:
        dic[p].append(y)
    else:
        dic[p] = [y]

result = []
for n in range(M):
    result.append(1)
    if not P[n] in dic:
        continue
    for i in range(n):
        if P[n] == P[i]:
            if Y[n] > Y[i]:
                result[n] += 1
            else:
                result[i] += 1


for x, y in zip(P, result):
    x, y = str(x), str(y)
    print('0'*(6-len(x))+x+'0'*(6-len(y))+y)

Submission status: Time Limit Exceeded

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

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

result = []
for n in range(M):
    result.append(1)
    for i in range(n):
        if P[n] == P[i]:
            if Y[n] > Y[i]:
                result[n] += 1
            else:
                result[i] += 1


for x, y in zip(P, result):
    x, y = str(x), str(y)
    print('0'*(6-len(x))+x+'0'*(6-len(y))+y)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
p = [list(map(int, input().split())) for i in range(m)]
l = []
for i in range(m):
    l.append([i])
for i in range(m):
    l[i].append(p[i][1])
p.sort(key=lambda x: x[1])
cnt = [0 for i in range(n+1)]
for i in range(m):
    cnt[p[i][0]] += 1
    for j in range(m):
        if p[i][1] == l[j][1]:
            l[j].append(str(p[i][0]).zfill(6)+str(cnt[p[i][0]]).zfill(6))
            break
for i in range(m):
    print(l[i][2])

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
n, m = map(int, input().split())
py = []
dict_p = {}
for i in range(m):
    p, y = map(int, input().split())
    py.append((p, y))
    if p not in dict_p.keys():
        dict_p[p] = list()

    dict_p[p].append(y)
#print(dict_p)
for values in dict_p.values():
    values.sort()

for p, y in py:
    x = bisect_left(dict_p[p], y)
    ans = "{:006}".format(p) + "{:006}".format(x+1)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
n, m = map(int, input().split())
p, y = [0]*m, [0]*m
dict_p = {}
for i in range(m):
    p[i], y[i] = map(int, input().split())
    if p[i] not in dict_p.keys():
        dict_p[p[i]] = list()

    dict_p[p[i]].append(y[i])
#print(dict_p)
ans = [0]*m
for i in range(m):
    dict_p[p[i]].sort()

for i in range(m):
    x = bisect_left(dict_p[p[i]], y[i])
    ans = "{:006}".format(p[i]) + "{:006}".format(x+1)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
n, m = map(int, input().split())
p, y = [0]*m, [0]*m
dict_p = {}
for i in range(m):
    p[i], y[i] = map(int, input().split())
    if p[i] not in dict_p.keys():
        dict_p[p[i]] = list()

    dict_p[p[i]].append(y[i])
#print(dict_p)
ans = [0]*m
for i in range(m):
    dict_p[p[i]].sort()
    x = bisect_left(dict_p[p[i]], y[i])
    ans = "{:006}".format(p[i]) + "{:006}".format(x+1)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
p = {str(i):[] for i in range(1,n+1)}
l = []
for i in range(m):
    t = input().split()
    l.append((t[0],int(t[1])))
    p[t[0]].append(int(t[1]))
for i in range(1,n+1):
    p[str(i)].sort()
for t in l:
    print(t[0].zfill(6)+str(p[t[0]].index(t[1])+1).zfill(6))

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
p, y = [0]*m, [0]*m
dict_p = {}
for i in range(m):
    p[i], y[i] = map(int, input().split())
    if p[i] not in dict_p.keys():
        dict_p[p[i]] = list()

    dict_p[p[i]].append(y[i])
#print(dict_p)
ans = [0]*m
for i in range(m):
    dict_p[p[i]].sort()
    l = 0
    r = len(dict_p[p[i]])
    while r-l > 1:
        mid = (l+r)//2
        if dict_p[p[i]][mid] <= y[i]:
            l = mid
        elif dict_p[p[i]][mid] > y[i]:
            r = mid

    i0 = l + 1
    p0 = p[i]
    ans = str("{:0=6}".format(p0)) + str("{:0=6}".format(i0))
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
p, y = [0]*m, [0]*m
dict_p = {}
for i in range(m):
    p[i], y[i] = map(int, input().split())
    if p[i] not in dict_p.keys():
        dict_p[p[i]] = list()

    dict_p[p[i]].append(y[i])
#print(dict_p)
ans = [0]*m
for i in range(m):
    dict_p[p[i]].sort()
    r = dict_p[p[i]].index(y[i]) + 1
    l = p[i]
    ans = str("{:0=6}".format(l)) + str("{:0=6}".format(r))
    print(ans)

Submission status: Time Limit Exceeded

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

def main():
    N, M = map(int, readline().rstrip().split())
    inp = [list(map(int, readline().rstrip().split())) for _ in range(M)]
    pref = {}
    for p, y in inp:
        pref.setdefault(p, [])
        pref[p].append(y)

    for key, val in pref.items():
        pref[key] = sorted(val)
        
    res = []
    for p, city in inp:
        cities = pref[p]
        id = str(p).zfill(6) + str(cities.index(city)+1).zfill(6)
        res.append(id)
    
    print(*res, sep='\n')

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def main():
    N, M = map(int, readline().rstrip().split())
    inp = [list(map(int, readline().rstrip().split())) for _ in range(M)]
    pref = {}
    for p, y in inp:
        pref.setdefault(p, [])
        pref[p].append(y)

    res = []
    for p, city in inp:
        cities = sorted(pref[p])
        id = str(p).zfill(6) + str(cities.index(city)+1).zfill(6)
        res.append(id)
    
    print(*res, sep='\n')

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
res = []
dic = {}
for i in range(m):
    p,y = map(int,input().split())
    res.append([p,y])
    if p not in dic:
        dic[p] = [y]
    else:
        dic[p].append(y)
        dic[p] = sorted(dic[p])        
for i in range(m):
    res[i][1] = dic[res[i][0]].index(res[i][1])+1
    print(str(res[i][0]).zfill(6)+str(res[i][1]).zfill(6))

Submission status: Time Limit Exceeded

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

#print("市i", "県P", "Y年")

dict_ = {}

for city in cities:
    #print(i, city)
    p = city[0]
    y = city[1]
    if not p in dict_:
        dict_[p] = []
    dict_[p].append(y)



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

#print(dict_)

#print("市i", "県P", "Y年")
for city in cities:
    p = city[0]
    y = city[1]
    number = dict_[p].index(y)+1
    #print(i, p, y, number)
    print(str(p).zfill(6)+str(number).zfill(6))

Submission status: Time Limit Exceeded

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

#print("市i", "県P", "Y年")

dict_ = {}

for i, city in enumerate(cities):
    #print(i, city)
    p = city[0]
    y = city[1]
    if not p in dict_:
        dict_[p] = []
    dict_[p].append(y)



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

#print(dict_)

#print("市i", "県P", "Y年")
for i, city in enumerate(cities):
    p = city[0]
    y = city[1]
    number = dict_[p].index(y)+1
    #print(i, p, y, number)
    print(str(p).zfill(6)+str(number).zfill(6))

Submission status: Time Limit Exceeded

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)


for item in range(n+1):
    p2year[item].sort()

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

Submission status: Time Limit Exceeded

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

py=[]
#初期値が0の辞書
from collections import defaultdict
p2year = defaultdict(lambda: []) 

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


for item in p2year.keys():
    p2year[item].sort()

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

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split()) #N個の県、M個の市
city_info = [] #要素０は０市の情報[P県、０市が誕生したY年]
Pref_info = [[] for _ in range(N)] #県P情報[要素０は０県。[市が誕生した年Y]
for i in range(M):
    P,Y = map(int,input().split())
    city_info.append([P-1, Y])
    Pref_info[P - 1].append(Y)
for i in Pref_info:
    i.sort()
    
#print("city_info = " + str(city_info))
#print("Pref_info = " + str(Pref_info))
for p,y in city_info:
    x = Pref_info[p].index(y) + 1 #市が誕生した順番を取得
    print("{0:0>6}".format(p+1) + "{0:0>6}".format(x))

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
city_for_pre = [[] for _ in range(N)]
#それぞれの件に属する市のリスト
city_list = {}
for m in range(M):
  Pi, Yi = map(int, input().split())
  city_list[m] = (Pi-1, Yi-1)
  city_for_pre[Pi-1].append(Yi-1)

import numpy as np
for city_id in city_list:
  prefec = city_list[city_id][0] #今回のcityの属する県
  Y =city_list[city_id][1] #今回のcityの建設年
  Y_list = city_for_pre[prefec] #今回のcityの属する県の全てのYear
  X = sum(np.array(Y_list) < Y) + 1

  ho = 6 - len(str(prefec+1))
  kami = '0'*ho + str(prefec+1)
  ho = 6 - len(str(X))
  shimo = '0'*ho + str(X)
  print(kami+shimo)

Submission status: Time Limit Exceeded

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)
        ys[i]=Y
    tset=[]
    tseti=[]
    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=heappop(t1)
            tx=str(j+1).zfill(6)
            tset.append(p+tx)
            tseti.append(t)
            j+=1
    for y in ys:
        i=tseti.index(y)
        print(tset[i])





if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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)
        ys[i]=Y
    tset=[]
    tseti=[]
    for i in range(N+1):
        t1=tot[i]
        if len(t1)<1:continue
        p=str(i)
        if len(p)<6:
            p='0'*(6-len(p))+p
        j=0
        while len(t1):
            t=heappop(t1)
            tx=str(j+1)
            if len(tx)<6:
                tx='0'*(6-len(tx))+tx
            tset.append(p+tx)
            tseti.append(t)
            j+=1
    for y in ys:
        i=tseti.index(y)
        print(tset[i])





if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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(M):
        P, Y = map(int, input().split())
        tot[P].append(Y)
        ys[i]=Y
    tset=[]
    tseti=[]
    for i in range(N+1):
        t1=tot[i]
        if len(t1)<1:continue
        p=str(i)
        if len(p)<6:
            p='0'*(6-len(p))+p
        t1.sort()
        for j,t in enumerate(t1):
            tx=str(j+1)
            if len(tx)<6:
                tx='0'*(6-len(tx))+tx
            tset.append(p+tx)
            tseti.append(t)
    for y in ys:
        i=tseti.index(y)
        print(tset[i])





if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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
    while p:
        heapq.heapify(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: Time Limit Exceeded

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
    while p:
        heapq.heapify(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: Time Limit Exceeded

Solution code:
import bisect
N,M=map(int,input().split())
py=[list(map(int,input().split())) for _ in range(M)]
dp=[[] for _ in range(N)]
#print(dp)
for i in range(M):
    if py[i][1] not in dp[py[i][0]-1]:    
        dp[py[i][0]-1].insert(bisect.bisect_left(dp[py[i][0]-1],py[i][1]),py[i][1])

for i in range(M):
    print(str(py[i][0]).rjust(6,"0")+str(dp[py[i][0]-1].index(py[i][1])+1).rjust(6,"0"))

#print(p)
#print(y)
#print(dp)

Submission status: Time Limit Exceeded

Solution code:
import bisect
N,M=map(int,input().split())
p=[]
y=[]
dp=[[] for _ in range(N)]
#print(dp)
for i in range(M):
    P,Y=map(int,input().split())
    p.append(P)
    y.append(Y)
    if Y not in dp[P-1]:    
        dp[P-1].insert(bisect.bisect_left(dp[P-1],Y),Y)

for i in range(M):
    print(str(p[i]).rjust(6,"0")+str(dp[p[i]-1].index(y[i])+1).rjust(6,"0"))

#print(p)
#print(y)
#print(dp)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

n, m = map(int, input().split())
prefectures = [list(map(int, input().split())) for _ in range(m)]
ID = defaultdict(list)

for prefecture in prefectures:
    p, y = prefecture
    ID[p].append(y)

for k, v in ID.items():
    v.sort()

for prefecture in prefectures:
    p, y = prefecture
    order = ID[p].index(y) + 1
    print('{:006}{:006}'.format(p, order))

Submission status: Time Limit Exceeded

Solution code:
import bisect
N,M=map(int,input().split())
p=[]
y=[]
dp=[[] for _ in range(N)]
#print(dp)
for i in range(M):
    P,Y=map(int,input().split())
    p.append(P)
    y.append(Y)
    if Y not in dp[P-1]:    
        dp[P-1]+=[Y]
        #print(dp[P-1])
#print(dp)
for n in range(N):
    dp[n]=sorted(dp[n])
for i in range(M):
    print(str(p[i]).rjust(6,"0")+str(bisect.bisect_left(dp[p[i]-1],y[i])+1).rjust(6,"0"))

#print(p)
#print(y)
#print(dp)

Submission status: Time Limit Exceeded

Solution code:
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
    while p:
        heapq.heapify(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: Time Limit Exceeded

Solution code:
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
    while p:
        heapq.heapify(p)
        temp = heapq.heappop(p)
        ans[temp[1]] = ''.join([str(prefnumber).zfill(6),str(count).zfill(6)])
        count += 1
for a in ans:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
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
    while p:
        heapq.heapify(p)
        temp = heapq.heappop(p)
        ans[temp[1]] = str(prefnumber).zfill(6) + str(count).zfill(6)
        count += 1
for a in ans:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
lst = [list(map(int,input().split())) for _ in range(m)]
pf = [(i, []) for i in range(100010)]
for p,y in lst:
    pf[p][1].append(y)
for i in range(len(pf)):
    l = sorted(pf[i][1])
    pf[i] = (i, l)
for p,y in lst:
    print(str(p).zfill(6)+str(pf[p][1].index(y)+1).zfill(6))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

x = sorted(lst, key=lambda x:x[1])
dic = {}
for p,y in x:
    if p in dic.keys():
        dic[p].append(y)
    else:
        dic[p] = [y]
for p,y in lst:
    print(str(p).zfill(6)+str(dic[p].index(y)+1).zfill(6))

Submission status: Time Limit Exceeded

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

ans = [""] * m
b = ""
cnt = 1
for p,y in py:
  if b == p: cnt += 1
  else:
    b = p
    cnt = 1
  a = [str(p), str(cnt)]
  if len(str(p)) < 6: a[0] = "0"*(6-len(str(p))) + str(p)
  if len(str(cnt)) < 6: a[1] = "0"*(6-len(str(cnt))) + str(cnt)
  i = PY.index([p, y])
  ans[i] = a[0] + a[1]
for v in ans: print(v)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
dic = {}
lst = [list(map(int,input().split())) for _ in range(m)]
for p,y in lst:
    if p in dic.keys():
        dic[p].append(y)
    else:
        dic[p] = [y]
nx_dic = {}
for k, v in dic.items():
    nx_dic[k] = sorted(v)

for p,y in lst:
    print(str(p).zfill(6)+str(nx_dic[p].index(y)+1).zfill(6))

Submission status: Time Limit Exceeded

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].insert(bisect_right(dic[p-1], y), y)
    shi[i] = (p, y)

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

Submission status: Time Limit Exceeded

Solution code:
n, m =  map(int, input().split())
py = [map(int, input().split()) for _ in range(m)]
p, y = [list(i) for i in zip(*py)]
pre = {}
for i in range(m):
    if p[i] not in pre.keys():
        pre[p[i]] = []
    pre[p[i]].append(y[i])
for i in pre.keys():
    pre[i].sort()
for i in range(m):
    print(str(p[i]*(10**6)+(pre[p[i]].index(y[i])+1)).zfill(12))

Submission status: Time Limit Exceeded

Solution code:
n, m =  map(int, input().split())
py = [map(int, input().split()) for _ in range(m)]
p, y = [list(i) for i in zip(*py)]
pre = {}
for i in range(m):
    if p[i] not in pre.keys():
        pre[p[i]] = []
    pre[p[i]].append(y[i])
for i in pre.keys():
    pre[i].sort()
for i in range(m):
    num = str(p[i]*(10**6)+(pre[p[i]].index(y[i])+1))
    while len(num) < 12:
        num = '0' + num
    print(num)

Submission status: Time Limit Exceeded

Solution code:
n, m =  map(int, input().split())
py = [map(int, input().split()) for _ in range(m)]
p, y = [list(i) for i in zip(*py)]
pre = {}
for i in range(m):
    if p[i] not in pre.keys():
        pre[p[i]] = []
    pre[p[i]].append(y[i])
for i in range(n):
    if i+1 in pre.keys():
        pre[i+1].sort()
for i in range(m):
    num = str(p[i]*(10**6)+(pre[p[i]].index(y[i])+1))
    while len(num) < 12:
        num = '0' + num
    print(num)

Submission status: Time Limit Exceeded

Solution code:
n, m =  map(int, input().split())
plist=[]
ylist = []
n0list=[]
for i in range(m):
    p, y =  map(int, input().split())
    plist.append(p)
    ylist.append(y)
    n0list.append(1)
    for j in range(i):
        if p == plist[j]:
            if y > ylist[j]:
                n0list[i] = n0list[i]+1
            else:
                n0list[j] = n0list[j]+1
for i in range(m):
    num = str(plist[i]*(10**6)+n0list[i])
    while len(num) < 12:
        num = '0' + num
    print(num)

Submission status: Time Limit Exceeded

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

pref_city=[[] for i in range(N)]

for r in PY:
    pref_city[r[0]-1].append(r[1])
pref_city_sorted=[]
for cities in pref_city:
    pref_city_sorted.append(sorted(cities))

for r in PY:
    order=pref_city_sorted[r[0]-1].index(r[1])+1
    print('{a:06}{b:06}'.format(a=r[0],b=order))

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
ab = []
cost = [[] for _ in range(n+1)]
for _ in range(m):
    a, b = (int(x) for x in input().split())
    ab.append([a, b])
    cost[a].append(b)
 
check = [0]*(n+1)
 
#print(cost)
for i,j in ab:
    if check[i] == 0:
        cost[i].sort()
        check[i] = 1
    ID = cost[i].index(j)+1
    i = str(i)
    i = (6-len(i))*'0'+i
    ID = str(ID)
    ID = (6-len(ID))*'0'+ID
    print(i+ID)