Overview

This problem asks us to reconstruct the original permutation \(P\), given for each person with height \(x\) the number of people \(A_x\) standing in front of them who are taller than them. By considering people in increasing order of height, we can uniquely determine the position each person should be placed in. This can be processed efficiently using a Binary Indexed Tree (BIT).

Analysis

Determining Positions in Increasing Order

Let us consider whether to determine the permutation from left to right (by position) or in increasing order of values. Focusing on the fact that the number of people taller than height \(x\) is given, let us consider determining where people are placed in the line in increasing order of height (\(x = 1, 2, \dots, N\)).

At the moment we determine the position of the person with height \(x\), the situation is as follows: - People shorter than them (\(1, 2, \dots, x - 1\)) have already been placed somewhere in the line. - The empty slots where no one has been placed yet will definitely be filled later by people taller than them (\(x + 1, \dots, N\)).

Therefore, the condition that “there are \(A_x\) people taller than \(x\) in front of \(x\)” can be rephrased as: “there are exactly \(A_x\) empty slots before the position where \(x\) is placed.”

In other words, the person with height \(x\) must be placed in the \((A_x + 1)\)-th remaining empty slot from the left at that point.

Naive Approach and Its Limitations

Consider a naive method where we manage the unoccupied slots using an array and, for each person, count the empty slots from the left to find the \((A_x + 1)\)-th one. However, this method takes \(O(N)\) time to find the empty slot each time, resulting in an overall time complexity of \(O(N^2)\). Since \(N \le 2 \times 10^5\) in this problem, this will exceed the time limit (TLE).

Optimization Approach

The operations we want to perform are the following two: 1. Find the position of the \(k\)-th (\(k = A_x + 1\)) unoccupied slot from the front. 2. Mark that slot as “occupied”.

If we maintain an array where each slot is \(1\) if it is empty and \(0\) if it is occupied, the “\(k\)-th empty slot from the front” corresponds to the “smallest index whose prefix sum equals \(k\)”. This can be processed efficiently in \(O(\log N)\) per operation using a Binary Indexed Tree (BIT) or a segment tree.

Algorithm

1. Create a BIT of length \(N\) and initialize all elements to \(1\) (all slots are empty).
2. For \(x = 1, 2, \dots, N\) in order, do the following:
   • Binary search on the BIT to find the position \(pos\) where the prefix sum is \(A_x + 1\).
   • Place \(x\) at the \(pos\)-th position of the permutation (\(P_{pos} = x\)).
   • Since slot \(pos\) is now occupied, subtract \(1\) at index \(pos\) in the BIT (updating \(1 \to 0\)).
3. Output the reconstructed permutation \(P\).

Complexity

• Time Complexity: \(O(N \log N)\)
  • Binary lifting on a BIT takes \(O(\log N)\) per query. Performing this for all \(N\) people gives an overall time complexity of \(O(N \log N)\), which easily passes within the time limit.
• Space Complexity: \(O(N)\)
  • \(O(N)\) memory is used to store the input array, the BIT, and the answer array.

Implementation Notes

• Binary Lifting on BIT (Binary Search on BIT): Usually, binary searching on a BIT can be implemented in \(O(\log^2 N)\) by calling a BIT prefix sum query inside a standard binary search. However, by taking advantage of the BIT’s structure and jumping bit-by-bit from higher powers of two, it can be implemented in \(O(\log N)\). For the constraint \(N \le 2 \times 10^5\), since \(2^{18} = 262,144 \ge N\), we can set the initial step size to \(2^{18}\) (1 << 18) and search downwards from the largest bit.

• Specifying \(k\): Note that since there are \(A_x\) empty slots before this person, the slot we are looking for is the \((A_x + 1)\)-th empty slot.

  Source Code

#include <iostream>
#include <vector>

using namespace std;

struct BIT {
    int n;
    vector<int> tree;
    BIT(int n) : n(n), tree(n + 1, 0) {}

    void add(int i, int delta) {
        for (; i <= n; i += i & -i) tree[i] += delta;
    }

    int find_kth(int k) {
        int idx = 0;
        for (int i = 1 << 18; i > 0; i >>= 1) {
            if (idx + i <= n && tree[idx + i] < k) {
                idx += i;
                k -= tree[idx];
            }
        }
        return idx + 1;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    if (!(cin >> N)) return 0;

    vector<int> A(N + 1);
    for (int i = 1; i <= N; ++i) {
        cin >> A[i];
    }

    BIT bit(N);
    for (int i = 1; i <= N; ++i) {
        bit.add(i, 1);
    }

    vector<int> P(N + 1);
    for (int x = 1; x <= N; ++x) {
        int pos = bit.find_kth(A[x] + 1);
        P[pos] = x;
        bit.add(pos, -1);
    }

    for (int i = 1; i <= N; ++i) {
        cout << P[i] << (i == N ? "" : " ");
    }
    cout << "\n";

    return 0;
}

---

This editorial was generated by gemini-3.8-flash-high.