Permutation Restoration (Codeforces 1701D)
Tags: Greedy, two pointers

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.

Input: 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$$$. 

Output: 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.


Sample Inputs:
4
4
0 2 0 1
2
1 1
5
0 0 1 4 1
3
0 1 3

Sample Outputs:
2 1 4 3 
1 2 
3 4 2 1 5 
3 2 1

Solution (Python):
import heapq
for _ in range(int(input())):
    n = int(input())
    b = map(int, input().split())
    u = sorted((((i + 1) // (x + 1), n if x == 0 else (i + 1) // x, i) for (i, x) in enumerate(b)))
    a = [0] * n
    heap = []
    j = 0
    for i in range(n):
        while j < n and u[j][0] <= i:
            heapq.heappush(heap, u[j][1:])
            j += 1
        a[heapq.heappop(heap)[1]] = i + 1
    print(*a)

Solution (Python):
from sys import stdin
input = lambda : stdin.readline()[:-1]
from heapq import heappop, heappush

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    L = [[] for i in range(n + 1)]
    for i in range(n):
        if a[i] == 0:
            L[i + 2].append((i, n))
        else:
            L[(i + 1) // (a[i] + 1) + 1].append((i, (i + 1) // a[i]))
    hq = []
    ans = [0] * n
    for l in range(1, n + 1):
        for (i, r) in L[l]:
            heappush(hq, (r, i))
        (_, id) = heappop(hq)
        ans[id] = l
    print(*ans)
for _ in range(int(input())):
    solve()

Solution (Python):
import heapq

def solve(arr):
    ranges_begin = [[] for _ in range(len(arr) + 1)]
    for j in range(len(arr)):
        val = arr[j]
        i = j + 1
        if val == 0:
            min_real = i + 1
            max_real = len(arr)
        else:
            max_real = i // val
            if i % (val + 1) == 0:
                min_real = i // (val + 1) + 1
            else:
                min_real = i // (val + 1) + 1
        ranges_begin[max_real].append((-min_real, j))
    res = [0 for _ in range(len(arr))]
    my_heap = []
    for val in range(len(arr), 0, -1):
        for r in ranges_begin[val]:
            heapq.heappush(my_heap, r)
        mini_of_heap = heapq.heappop(my_heap)
        res[mini_of_heap[1]] = val
    return res
T = int(input())
for _ in range(T):
    n = int(input())
    arr = list(map(int, input().split()))
    res_arr = solve(arr)
    print(' '.join(map(str, res_arr)))