Cod sursa(job #1793983)

Utilizator grimmerFlorescu Luca grimmer Data 31 octombrie 2016 19:00:19
Problema Schi Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <fstream>
using namespace std;

ifstream fin("schi.in");
ofstream fout("schi.out");

const int NMAX = 30000;
int aint[NMAX + 5], pos[NMAX + 5], n, final_pos[NMAX + 5];

void Update(int node, int l, int r, int pos, int val){
    if(l == r){
        aint[node] = val;
        return;
    }

    int m = (l + r) / 2;
    int Ls = node * 2, Rs = Ls + 1;

    if(pos <= m){
        Update(Ls, l, m, pos, val);
    }
    else{
        Update(Rs, m + 1, r, pos, val);
    }

    aint[node] = aint[Ls] + aint[Rs];

}

int Query_search(int node, int l, int r, int sum){
    if(l == r){
        return l;
    }

    int m = (l + r) / 2, ans;
    int Ls = node * 2, Rs = Ls + 1;

    if(sum <= aint[Ls]){
        ans = Query_search(Ls, l, m, sum);
    }
    else{
        ans = Query_search(Rs, m + 1, r, sum - aint[Ls]);
    }

    return ans;
}

int main()
{
    int i, p;

    fin>>n;

    for(i = 1; i <= n; ++i){
        fin>>pos[i];
        Update(1, 1, n, i, 1);
    }

    for(i = n; i >= 1; --i){
        p = Query_search(1, 1, n, pos[i]);
        Update(1, 1, n, p, 0);
        final_pos[p] = i;
    }

    for(i = 1; i <= n; ++i){
        fout<< final_pos[i] << "\n";
    }

    return 0;
}