Cod sursa(job #2015290)

Utilizator Alex18maiAlex Enache Alex18mai Data 25 august 2017 17:15:21
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 kb
#include <fstream>

using namespace std;

ifstream cin ("schi.in");
ofstream cout ("schi.out");

int n;
int Arb[120000];
int A[30005];
int ans[30005];

int biggest_2_pow(int nr){
    int i=1;
    while(1){
        if (i > nr){
            return (i >> 1);
        }
        i <<= 1;
    }
}

void Update (int nod, int st, int dr, int pos, int val){
    if (st == dr){
        Arb[nod] = val;
        return;
    }
    int mij = (st + dr) / 2;
    if (pos <= mij){
        Update(nod * 2, st, mij, pos, val);
    }
    else{
        Update(nod * 2 + 1, mij + 1, dr, pos, val);
    }
    Arb[nod] = Arb[nod * 2] + Arb[nod * 2 + 1];
}

void Querry (int nod, int st, int dr, int pos, int &sum){
    if (st == dr){
        sum += 1;
        return;
    }
    int mij = (st + dr) / 2;
    if (mij >= pos){
        Querry(nod * 2, st, mij, pos, sum);
    }
    else{
        sum += Arb[nod * 2];
        Querry(nod * 2 + 1, mij + 1, dr, pos, sum);
    }
}

int main() {
    cin>>n;
    int start = biggest_2_pow(n);
    for (int i=1; i<=n; i++){
        Update (1, 1, n, i, 1);
        cin>>A[i];
    }
    for (int i=n; i>=1; i--){
        int sol = 0;
        for (int step = start; step > 0; step >>= 1){
            int s = 0;
            Querry(1, 1, n, sol + step, s);
            //cout<<s<<'\n';
            if (sol + step <=n && s <= A[i]){
                sol += step;
            }
        }
        //cout<<sol<<'\n';
        ans[sol] = i;
        Update (1, 1, n, sol, 0);
    }
    for (int i=1; i<=n; i++){
        cout<<ans[i]<<'\n';
    }
    return 0;
}