Scoring Subsequences (Codeforces 1794C)
Tags: Greedy, two pointers

The score of a sequence $$$[s_1, s_2, \ldots, s_d]$$$ is defined as $$$\displaystyle \frac{s_1\cdot s_2\cdot \ldots \cdot s_d}{d!}$$$, where $$$d!=1\cdot 2\cdot \ldots \cdot d$$$. In particular, the score of an empty sequence is $$$1$$$.For a sequence $$$[s_1, s_2, \ldots, s_d]$$$, let $$$m$$$ be the maximum score among all its subsequences. Its cost is defined as the maximum length of a subsequence with a score of $$$m$$$.You are given a non-decreasing sequence $$$[a_1, a_2, \ldots, a_n]$$$ of integers of length $$$n$$$. In other words, the condition $$$a_1 \leq a_2 \leq \ldots \leq a_n$$$ is satisfied. For each $$$k=1, 2, \ldots , n$$$, find the cost of the sequence $$$[a_1, a_2, \ldots , a_k]$$$. A sequence $$$x$$$ is a subsequence of a sequence $$$y$$$ if $$$x$$$ can be obtained from $$$y$$$ by deletion of several (possibly, zero or all) elements.

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.The first line of each test case contains an integer $$$n$$$ ($$$1\le n\le 10^5$$$) — the length of the given sequence. The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1\le a_i\leq n$$$) — the given sequence. It is guaranteed that its elements are in non-decreasing order.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5\cdot 10^5$$$.

Output: For each test case, output $$$n$$$ integers — the costs of sequences $$$[a_1, a_2, \ldots , a_k]$$$ in ascending order of $$$k$$$.

Note: In the first test case:   The maximum score among the subsequences of $$$[1]$$$ is $$$1$$$. The subsequences $$$[1]$$$ and $$$[]$$$ (the empty sequence) are the only ones with this score. Thus, the cost of $$$[1]$$$ is $$$1$$$.  The maximum score among the subsequences of $$$[1, 2]$$$ is $$$2$$$. The only subsequence with this score is $$$[2]$$$. Thus, the cost of $$$[1, 2]$$$ is $$$1$$$.  The maximum score among the subsequences of $$$[1, 2, 3]$$$ is $$$3$$$. The subsequences $$$[2, 3]$$$ and $$$[3]$$$ are the only ones with this score. Thus, the cost of $$$[1, 2, 3]$$$ is $$$2$$$.  Therefore, the answer to this case is $$$1\:\:1\:\:2$$$, which are the costs of $$$[1], [1, 2]$$$ and $$$[1, 2, 3]$$$ in this order.

Sample Inputs:
3
3
1 2 3
2
1 1
5
5 5 5 5 5

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

Solution (Python):
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    left = 0
    length = 1
    ans = []
    for x in range(n):
        if a[left] > length:
            ans.append(length)
            length += 1
        else:
            left += 1
            ans.append(length)
    print(' '.join([str(i) for i in ans]))

Solution (Python):
def print_sub(n, arr):
    r = '1 '
    per = 0
    per_score = 1
    for i in range(1, n):
        if arr[per] / (per_score + 1) < 1:
            r += f'{per_score} '
            per = per + 1
        else:
            per_score += 1
            r += f'{per_score} '
    print(r)
for t in range(int(input())):
    n = int(input())
    arr = list(map(int, input().split()))
    print_sub(n, arr)

Solution (Python):
def solve(s):
    l = list(map(int, s.split()))
    n = len(l)
    v = [0] * n
    resp = []
    a = 1
    for i in range(0, n):
        a -= v[i]
        resp.append(a)
        if i + l[i] < n:
            v[i + l[i]] += 1
        a += 1
    return ' '.join(map(str, resp))
n = int(input())
for i in range(n):
    m = int(input())
    s = input()
    print(solve(s))