In Republic of Atcoder, there are N prefectures, and a total of M cities that belong to…
- User
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, ...).
Examples
Input
2 3 1 32 2 63 1 12
Output
000001000002 000002000001 000001000001
Input
2 3 2 55 2 77 2 99
Output
000002000001 000002000002 000002000003
Assistant
We need to generate ID numbers for each city. Each city i has prefecture P_i and year Y_i. We need to order cities within each prefecture by year (since Y_i are all different, we can rank them by Y_i ascending: the earliest established city gets rank 1, then 2, etc.). Then the ID is: first 6 digits: P_i padded to 6 digits (leading zeros), last 6 digits: rank x padded to 6 digits.
But note that the statement says "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." It says "Prefecture i", which likely means "the prefecture that city i belongs to" i.e., Prefecture P_i. So yes.
We need to output ID for each city in the order of input (city 1..M). So we must compute rank for each city within its prefecture.
Constraints: N,M up to 1e5. So we can group cities by prefecture, sort each group by year, assign ranks, then output.
Implementation: read N,M. For i in 1..M, read P_i, Y_i. Store as tuple (P_i, Y_i, index=i). Then create dictionary mapping prefecture -> list of (year, index). For each prefecture, sort list by year. Then assign rank from 1 to len(list). For each (year, index) in sorted list, assign rank. Then create answer array of size M. For each city, compute id: f"{P_i:06d}{rank:06d}". Print each.
Time O(M log M) worst-case if all in one prefecture; else O(M log M) overall due to sorting each group but total sum of sizes = M; but sorting each group individually is still total O(M log M) because sum of (size * log size) is ≤ M log M (by convexity). Actually worst-case: one group of size M => M log M. So fine.
Edge cases: prefecture with no cities ignored.
Now handle examples.
First example: N=2 M=3 City1: 1 32 City2: 2 63 City3: 1 12
Group prefecture 1: cities (32, idx1), (12, idx3) sorted by year => (12, idx3) rank1, (32, idx1) rank2. Prefecture 2: (63, idx2) rank1. Output: City1: P=1, rank=2 => 000001000002 City2: P=2, rank=1 => 000002000001 City3: P=1, rank=1 => 000001000001 matches.
Second example: All in prefecture 2, years: 55,77,99. Ranks: 1,2,3. IDs accordingly.
Thus solution is straightforward.
But careful: The note says there can be a prefecture with no cities; we ignore.
So code: read input, build list of cities. Then for each prefecture, sort its list by year. Then assign. Use zero-indexed for Python.
Pseudo:
def main(): import sys input = sys.stdin.readline N, M = map(int, input().split()) pref_cities = [[] for _ in range(N+1)] # index from 1 cities = [] # store (P, Y, i) for later? We can store in list and later assign rank. for i in range(1, M+1): P, Y = map(int, input().split()) cities.append((P, Y, i)) pref_cities[P].append((Y, i)) ranks = [0]*(M+1) # rank for each city index for p in range(1, N+1): lst = pref_cities[p] if not lst: continue lst.sort(key=lambda x: x[0]) # sort by year for rank, (y, idx) in enumerate(lst, start=1): ranks[idx] = rank out = [] for P, Y, i in cities: # We have rank already rank = ranks[i] out.append(f"{P:06d}{rank:06d}") sys.stdout.write("\n".join(out))
This works.
Potential pitfalls: N up to 100k, but M also up to 100k; using list of lists is fine.
Time complexity: O(N + M log avg) but fine.
Now consider memory: storing lists for each prefecture, total M entries; fine.
Thus answer.
But note: The problem statement says "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." It says "Prefecture i" but it's ambiguous. However from examples it's clear.
Now we can output.
Thus final solution.
But the user likely wants a response that explains solution, possibly with code. Since it's a ChatGPT reasoning, we produce final answer: explanation + code. Typically we respond with a formatted solution.
Thus provide Python code.
Add newline at end? It's okay.
We'll provide a solution.
Now consider that there is possibility of having to preserve input order: output in ascending order of indices, i.e., city 1,2,...M. That's what we do.
Thus final. We need to assign to each city a 12-digit ID composed of two 6-digit parts: the prefecture number (padded) and the city's order of establishment within that prefecture (padded). The cities are given with their prefecture and year; years are unique. For each prefecture we sort its cities by year to obtain the establishment order, assign ranks, then format the ID.
The solution groups cities by prefecture, sorts each group, records the rank for each original index, and finally outputs the IDs in the original order.
import sys def main(): input = sys.stdin.readline N, M = map(int, input().split()) # pref_cities[p] will hold (year, index) for cities in prefecture p pref_cities = [[] for _ in range(N + 1)] # original list to keep input order for output cities = [] for i in range(1, M + 1): P, Y = map(int, input().split()) cities.append((P, Y, i)) pref_cities[P].append((Y, i)) # ranks[i] = rank of city i (1-indexed) ranks = [0] * (M + 1) for p in range(1, N + 1): lst = pref_cities[p] if not lst: continue lst.sort(key=lambda x: x[0]) # sort by year for rank, (_, idx) in enumerate(lst, start=1): ranks[idx] = rank out_lines = [] for P, _, idx in cities: rank = ranks[idx] out_lines.append(f"{P:06d}{rank:06d}") sys.stdout.write("\n".join(out_lines)) if __name__ == "__main__": main()