Lexicographically Largest (Codeforces 1930C)
Tags: Greedy, binary search

Stack has an array $$$a$$$ of length $$$n$$$. He also has an empty set $$$S$$$. Note that $$$S$$$ is not a multiset.He will do the following three-step operation exactly $$$n$$$ times:  Select an index $$$i$$$ such that $$$1 \leq i \leq |a|$$$.  Insert$$$^\dagger$$$ $$$a_i + i$$$ into $$$S$$$.  Delete $$$a_i$$$ from $$$a$$$. Note that the indices of all elements to the right of $$$a_i$$$ will decrease by $$$1$$$. Note that after $$$n$$$ operations, $$$a$$$ will be empty.Stack will now construct a new array $$$b$$$ which is $$$S$$$ sorted in decreasing order. Formally, $$$b$$$ is an array of size $$$|S|$$$ where $$$b_i$$$ is the $$$i$$$-th largest element of $$$S$$$ for all $$$1 \leq i \leq |S|$$$.Find the lexicographically largest$$$^\ddagger$$$ $$$b$$$ that Stack can make.$$$^\dagger$$$ A set can only contain unique elements. Inserting an element that is already present in a set will not change the elements of the set.$$$^\ddagger$$$ An array $$$p$$$ is lexicographically larger than a sequence $$$q$$$ if and only if one of the following holds:   $$$q$$$ is a prefix of $$$p$$$, but $$$p \ne q$$$; or  in the first position where $$$p$$$ and $$$q$$$ differ, the array $$$p$$$ has a larger element than the corresponding element in $$$q$$$. Note that $$$[3,1,4,1,5]$$$ is lexicographically larger than $$$[3,1,3]$$$, $$$[\,]$$$, and $$$[3,1,4,1]$$$ but not $$$[3,1,4,1,5,9]$$$, $$$[3,1,4,1,5]$$$, and $$$[4]$$$.

Input: Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. The description of the test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 3 \cdot 10^5$$$) — the length of array $$$a$$$.The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_{n}$$$ ($$$1 \leq a_i \leq 10^9$$$) — the elements of array $$$a$$$.The sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.

Output: For each test case, output the lexicographically largest $$$b$$$.

Note: In the first test case, select $$$i=1$$$ in the first operation, insert $$$a_1 + 1 = 3$$$ in $$$S$$$, and delete $$$a_1$$$ from $$$a$$$. After the first operation, $$$a$$$ becomes $$$a=[1]$$$. In the second operation, we select $$$i=1$$$ again and insert $$$a_1 + 1 = 2$$$ in $$$S$$$. Thus $$$S=\{2, 3\}$$$, and $$$b = [3, 2]$$$.Note that if you select $$$i=2$$$ in the first operation, and $$$i=1$$$ in the second operation, $$$S=\{3\}$$$ as $$$3$$$ will be inserted twice, resulting in $$$b=[3]$$$.As $$$[3,2]$$$ is lexicographically larger than $$$[3]$$$, we should select $$$i=1$$$ in the first operation.In the second test case, in each operation, select the last element.

Sample Inputs:
3
2
2 1
5
1 100 1000 1000000 1000000000
3
6 4 8

Sample Outputs:
3 2 
1000000005 1000004 1003 102 2 
11 7 6

Solution (Python):
for _ in range(int(input())):
    n = int(input())
    x = [i + b + 1 for (i, b) in enumerate(map(int, input().split()))]
    x.sort(reverse=True)
    y = [2000000000.0]
    for a in x:
        if y[-1] > a:
            y.append(a)
        else:
            y.append(y[-1] - 1)
    print(' '.join(map(str, y[1:])))

Solution (Python):
import sys
input = sys.stdin.readline
print = sys.stdout.write

def solve():
    n = int(input())
    a = [*map(int, input().split())]
    for i in range(n):
        a[i] += i + 1
    a.sort(reverse=1)
    for i in range(1, n):
        a[i] = min(a[i], a[i - 1] - 1)
    return ' '.join(map(str, a))
print('\n'.join((solve() for _ in range(int(input())))))

Solution (Python):
t = int(input())

def f(n, a):
    new = []
    for i in range(n):
        new.append(a[i] + i + 1)
    return new
for _ in range(t):
    c = 10 ** 12
    array = []
    n = int(input())
    a = list(map(int, input().split()))
    new = f(n, a)
    new.sort(reverse=True)
    for i in range(n):
        new[i] = min(new[i], c - 1)
        c = min(c, new[i])
        new[i] = c
    string_list = [str(num) for num in new]
    result_string = ' '.join(string_list)
    print(result_string)