Permutation Restoration

题意翻译

## 题目描述 Monocarp 有一个长度为 $n$ ，由 $1$ ~ $n$ 构成的数组 $a$ ，其中每个元素在 $a$ 中出现且仅出现 $1$ 次。 现在 Monocarp 计算一个数组 $b$ ，使得 $b_i=\lfloor\frac{i}{a_i}\rfloor$ 。 现在给出 $b$ 数组，要求求出任意一组 $a$ 。 注意：保证对于所给出的 $b$ 至少有一组 $a$ 与之对应。 ## 输入格式 本题为多组数据。 第一行为一个整数 $t(1 \le t \le 10^5)$ ，代表数据组数。 接下来 $t$ 组，每组的第一行为一个整数 $n(1 \le n \le 5×10^5)$ 。 每组的第二行为 $n$ 个整数 $b_1,b_2,···,b_n(0 \le b_i \le n)$ 。 ## 输出格式 对于每组，输出 $n$ 对于给定数组 $b$ 的任意一组 $a$ 。

题目描述

Monocarp had a permutation $ a $ of $ n $ integers $ 1 $ , $ 2 $ , ..., $ n $ (a permutation is an array where each element from $ 1 $ to $ n $ occurs exactly once). Then Monocarp calculated an array of integers $ b $ of size $ n $ , where $ b_i = \left\lfloor \frac{i}{a_i} \right\rfloor $ . For example, if the permutation $ a $ is $ [2, 1, 4, 3] $ , then the array $ b $ is equal to $ \left[ \left\lfloor \frac{1}{2} \right\rfloor, \left\lfloor \frac{2}{1} \right\rfloor, \left\lfloor \frac{3}{4} \right\rfloor, \left\lfloor \frac{4}{3} \right\rfloor \right] = [0, 2, 0, 1] $ . Unfortunately, the Monocarp has lost his permutation, so he wants to restore it. Your task is to find a permutation $ a $ that corresponds to the given array $ b $ . If there are multiple possible permutations, then print any of them. The tests are constructed in such a way that least one suitable permutation exists.

输入输出格式

输入格式

The first line contains a single integer $ t $ ( $ 1 \le t \le 10^5 $ ) — number of test cases. The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 5 \cdot 10^5 $ ). The second line contains $ n $ integers $ b_1, b_2, \dots, b_n $ ( $ 0 \le b_i \le n $ ). Additional constrains on the input: - the sum of $ n $ over test cases does not exceed $ 5 \cdot 10^5 $ ; - there exists at least one permutation $ a $ that would yield this array $ b $ .

输出格式

For each test case, print $ n $ integers — a permutation $ a $ that corresponds to the given array $ b $ . If there are multiple possible permutations, then print any of them.

输入输出样例

输入样例 #1

4
4
0 2 0 1
2
1 1
5
0 0 1 4 1
3
0 1 3

输出样例 #1

2 1 4 3 
1 2 
3 4 2 1 5 
3 2 1

**题目大意：**
Monocarp有一个由1到n构成的长度为n的排列（数组）a，每个元素在a中恰好出现一次。然后Monocarp计算了一个大小为n的整数数组b，其中\( b_i = \left\lfloor \frac{i}{a_i} \right\rfloor \)。现在给出数组b，要求求出任意一组对应的排列a。保证至少存在一组排列a与给定的b相对应。

**输入数据格式：**
第一行包含一个整数t（1≤t≤10^5），代表测试用例的数量。
每个测试用例的第一行包含一个整数n（1≤n≤5×10^5）。
每个测试用例的第二行包含n个整数\( b_1, b_2, \dots, b_n \)（0≤\( b_i \)≤n）。
输入数据额外限制：
- 所有测试用例的n之和不超过5×10^5；
- 至少存在一组排列a能生成给定的数组b。

**输出数据格式：**
对于每个测试用例，输出n个整数，这是一组对应给定数组b的排列a。如果有多个可能的排列，输出其中任意一个。

**输入输出样例：**
**输入样例 #1：**
```
4
4
0 2 0 1
2
1 1
5
0 0 1 4 1
3
0 1 3
```
**输出样例 #1：**
```
2 1 4 3
1 2
3 4 2 1 5
3 2 1
```**题目大意：** Monocarp有一个由1到n构成的长度为n的排列（数组）a，每个元素在a中恰好出现一次。然后Monocarp计算了一个大小为n的整数数组b，其中\( b_i = \left\lfloor \frac{i}{a_i} \right\rfloor \)。现在给出数组b，要求求出任意一组对应的排列a。保证至少存在一组排列a与给定的b相对应。 **输入数据格式：** 第一行包含一个整数t（1≤t≤10^5），代表测试用例的数量。 每个测试用例的第一行包含一个整数n（1≤n≤5×10^5）。 每个测试用例的第二行包含n个整数\( b_1, b_2, \dots, b_n \)（0≤\( b_i \)≤n）。 输入数据额外限制： - 所有测试用例的n之和不超过5×10^5； - 至少存在一组排列a能生成给定的数组b。 **输出数据格式：** 对于每个测试用例，输出n个整数，这是一组对应给定数组b的排列a。如果有多个可能的排列，输出其中任意一个。 **输入输出样例：** **输入样例 #1：** ``` 4 4 0 2 0 1 2 1 1 5 0 0 1 4 1 3 0 1 3 ``` **输出样例 #1：** ``` 2 1 4 3 1 2 3 4 2 1 5 3 2 1 ```