#01 - Vị trí ban đầu
Xem PDF
Điểm:
1
Thời gian:
1.0s
Bộ nhớ:
512M
Input:
bàn phím
Output:
màn hình
Cho mảng \(A\) gồm \(n\) phần tử phân biệt. Gọi \(B\) là mảng \(A\) sau khi sắp xếp không giảm.
Gọi \(C_i\) là vị trí trên mảng \(A\) sao cho \(B_i = A_{C_i}\).
Hãy tính mảng \(C\), hay nói cách khác là hãy cho biết vị trí ban đầu trên mảng \(A\) của mỗi phần tử trên \(B\).
Input
- Dòng đầu tiên in ra số \(n\) \((n \leq 100000)\).
- Dòng thứ hai in ra \(n\) số nguyên \(A_1, A_2, \dots, A_n\) \((1 \leq A_i \leq 10^9)\).
Output
- In ra một dòng duy nhất gồm \(n\) số nguyên \(C_1, C_2, \dots, C_n\).
Scoring
- Subtask \(1\) (\(30\%\) số điểm): \(n \leq 1000\)
- Subtask \(2\) (\(30\%\) số điểm): \(A_i \leq 1000000\)
- Subtask \(3\) (\(40\%\) số điểm): không có giới hạn nào khác
Example
Test 1
Input
3
2 3 1Output
3 1 2
Bình luận
def find_original_indices(n, A):
indexed_A = [(value, index) for index, value in enumerate(A)]
indexed_A.sort()
C = [0] * n
for sorted_index, (value, original_index) in enumerate(indexed_A):
C[sorted_index] = original_index + 1
return C
n = int(input())
A = list(map(int, input().split()))
C = find_original_indices(n, A)
print(' '.join(map(str, C)))
khó phết
2 bình luận nữa