Overview

Given \(A_x\), the number of people taller than person \(x\) standing ahead of them, this problem asks us to reconstruct the original permutation \(P\). We can reconstruct it by placing people in ascending order of height into the “\((A_x+1)\)-th empty seat from the front”, which can be handled efficiently via binary search (binary lifting) on a Fenwick tree (BIT).

Analysis

Key Observation: Determining Positions from Shortest to Tallest

\(A_x\) is “the number of people who are ahead of the person with height \(x\) and have a height greater than \(x\)”. Note that people taller than \(x\) are precisely those with heights \(x+1, x+2, \dots, N\).

Therefore, let us consider placing people in ascending order of height: \(x = 1, 2, \dots, N\). At the moment we place the person with height \(x\):

• The only people whose seats are already decided are those with heights \(1, \dots, x-1\) (i.e., people shorter than \(x\)).
• The seats that are still empty will eventually be occupied by people with heights \(x, x+1, \dots, N\).

This means that any empty seat ahead of \(x\) will definitely be occupied by someone taller than \(x\) (all empty seats except \(x\)’s own seat will be filled by people with height at least \(x+1\)). Conversely, the occupied seats ahead of \(x\) contain only people shorter than \(x\).

Therefore:

The number of empty seats ahead of the position of the person with height \(x\) = \(A_x\)

In other words, the person with height \(x\) must be placed in the \((A_x+1)\)-th currently empty seat from the front. The constraint \(A_x \le N - x\) corresponds to the fact that there are \(N-x+1\) empty seats at this point, which guarantees that such a placement is always possible.

Concrete Example

For \(N = 4\), \(A = (2, 0, 1, 0)\):

Step	Empty Seats	Which Empty Seat	Placement
\(x=1\)	\(\{1,2,3,4\}\)	\(A_1+1 = 3\)	Position \(3\)
\(x=2\)	\(\{1,2,4\}\)	\(A_2+1 = 1\)	Position \(1\)
\(x=3\)	\(\{2,4\}\)	\(A_3+1 = 2\)	Position \(4\)
\(x=4\)	\(\{2\}\)	\(A_4+1 = 1\)	Position \(2\)

The resulting array is \(P = (2, 4, 1, 3)\). Verifying this indeed gives \(A=(2,0,1,0)\), which is correct.

Why a Naive Implementation is Too Slow

An implementation that “maintains empty seats in an array (or list) and linearly searches for the \((A_x+1)\)-th empty seat” or “pops from a Python list and shifts elements” takes \(O(N)\) per person, resulting in \(O(N^2)\) overall. For \(N = 2\times 10^5\), this requires around \(4\times 10^{10}\) operations, leading to TLE.

Thus, we need a data structure that can efficiently perform the operation: “find the \(k\)-th empty seat and mark it as occupied”.

Algorithm

Using a Fenwick tree (BIT), we maintain a value of \(1\) if position \(i\) is empty and \(0\) if it is occupied. Then:

• “Finding the \(k\)-th empty seat from the front” = “Finding the first position where the prefix sum is at least \(k\)”.

This can be handled in \(O(\log N)\) using binary search (binary lifting) on the BIT.

The procedure is as follows:

1. Initialize the BIT with all elements set to \(1\).
2. For \(x = 1, 2, \dots, N\):
   • Let \(k = A_x + 1\), and find the minimum position \(p\) where the prefix sum is at least \(k\) using binary search on the BIT.
   • \(P_p \leftarrow x\).
   • Add \(-1\) at position \(p\) (marking the seat as occupied).
3. Output \(P\).

Binary search on a BIT is a standard technique: halving bit from \(2^{\lfloor \log_2 N\rfloor}\) down to \(1\), if “\(pos + bit \le N\) and tree[pos+bit] < rem”, we update \(pos \mathrel{+}= bit\) and \(rem \mathrel{-}= \) tree[pos+bit]. When the loop finishes, \(pos\) is the “maximum prefix length whose prefix sum is strictly less than \(rem\)”. Therefore, the target position is \(pos+1\) in \(1\)-indexed representation, which corresponds to index \(pos\) in a \(0\)-indexed array.

Complexity

• Time complexity: \(O(N \log N)\) (binary search on the BIT and single-point update each take \(O(\log N)\) for each person)
• Space complexity: \(O(N)\)

Implementation Notes

• Initializing the BIT with all 1s in \(O(N)\): Simply setting tree[i] = i & (-i) (the least significant bit of \(i\)) constructs a Fenwick tree where all elements are \(1\). This is simpler and faster than calling add \(N\) times in \(O(N\log N)\).

• Beware of mixing up \(0\)-indexed and \(1\)-indexed representations: The BIT is \(1\)-indexed, while the output array P is \(0\)-indexed. As explained above, directly using the binary search result \(pos\) for P[pos] correctly aligns the indices.

• Fast I/O: Since \(N = 2\times 10^5\), in Python it is safer to read all input at once using sys.stdin.buffer.read().split() and output the result at once using ' '.join.

• Do not forget the \(+1\) in “the \((A_x+1)\)-th empty seat” (if \(A_x = 0\), it is the very first empty seat).

• As alternative approaches, one could also process people in descending order of height, or find the \(k\)-th empty seat by walking down a segment tree or using a balanced binary search tree; the underlying principle is the same.

  Source Code

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    A = list(map(int, data[1:1 + n]))
    tree = [0] * (n + 1)
    for i in range(1, n + 1):
        tree[i] = i & (-i)
    LOG = n.bit_length()
    top = 1 << LOG
    P = [0] * n
    for x in range(1, n + 1):
        rem = A[x - 1] + 1
        pos = 0
        bit = top
        while bit:
            nx = pos + bit
            if nx <= n:
                t = tree[nx]
                if t < rem:
                    pos = nx
                    rem -= t
            bit >>= 1
        P[pos] = x
        i = pos + 1
        while i <= n:
            tree[i] -= 1
            i += i & (-i)
    sys.stdout.write(' '.join(map(str, P)))

main()

---

This editorial was generated by claude5opus-high.