Proficient.
Put your skills to the test.

Problem summary

Athletes start in increasing number order at equal intervals and run at constant speeds. Given how many athletes overtake each athlete, reconstruct their unique finish order.

Constraints

2 ≤ N ≤ 1000000; input guarantees a unique valid answer.

Worked example

An independently prepared example for this explanation.

9
2
3
6
4
0
2
2
1
0

5
9
1
8
2
6
4
7
3

Solution analysis

1. An athlete starting earlier cannot overtake a later starter: at the later start they are already ahead, and constant speed makes any change of relative order occur at most once. Thus athlete i is overtaken precisely by larger-numbered athletes who finish before i.
2. Place athletes in increasing numerical order. The unfilled finish positions will eventually hold larger labels. If i reports c overtakes, place i in the (c+1)-st currently empty position. A Fenwick tree storing one for each empty position supports this selection and deletion in logarithmic time.
3. Athlete 1 reports 2, so takes finish position 3. Athlete 2 reports 3, so takes the fourth remaining slot, position 5. Continuing yields the supplied finish order.

Why it works

When placing i, every still-empty position will be occupied by a larger label. Choosing its (c+1)-st empty position puts exactly c larger athletes before it. Previously placed smaller athletes do not affect its overtake count. Every step is forced, proving both validity and uniqueness.

Watch out. Use rank among empty positions, not among all positions. Counts are zero-based but order-statistic selection is one-based.

An independently written complete program with standard headers.

#include<iostream>
#include<vector>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<int>tree(n+1),answer(n+1);
    for(int i=1;i<=n;++i){
        tree[i]=i&-i;
    }
    int highest=1;
    while(highest<=n/2){
        highest*=2;
    }
    for(int athlete=1;athlete<=n;++athlete){
        int rank;
        cin>>rank;
        ++rank;
        int position=0;
        // Binary lifting finds the last prefix containing fewer than rank holes.
        for(int step=highest;step>0;step/=2){
            int next=position+step;
            if(next<=n&&tree[next]<rank){
                rank-=tree[next];
                position=next;
            }
        }
        ++position;
        answer[position]=athlete;
        for(int j=position;j<=n;j+=j&-j){
            --tree[j];
        }
    }
    for(int position=1;position<=n;++position){
        cout<<answer[position]<<'\n';
    }
}