Cod sursa(job #3326609)

Utilizator AnSeDraAndrei Sebastian Dragulescu AnSeDra Data 29 noiembrie 2025 16:08:32
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.73 kb
#include <fstream>

using namespace std;

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

const int Nmax = 30005;

int n;
int pozitii_relative[Nmax], clasament[Nmax], aint[4 * Nmax];

void aint_build(int nod, int st, int dr){
    if(st == dr){
        aint[nod] = 1;
        return;
    }

    int mid = (st + dr) / 2;

    aint_build(2 * nod, st, mid);
    aint_build(2 * nod + 1, mid + 1, dr);

    aint[nod] = aint[2 * nod] + aint[2 * nod + 1];
}

void aint_update(int nod, int st, int dr, int poz){
    if(st == dr){
        aint[nod] = 0;
        return;
    }

    int mid = (st + dr) / 2;

    if(poz <= mid){
        aint_update(2 * nod, st, mid, poz);
    }
    else{
        aint_update(2 * nod + 1, mid + 1, dr, poz);
    }

    aint[nod] = aint[2 * nod] + aint[2 * nod + 1];
}

int aint_query(int nod, int st, int dr, int val, int pana_acum){
    if(st == dr){
        return st;
    }

    int mid = (st + dr) / 2;

    if(aint[2 * nod] + pana_acum >= val){
        return aint_query(2 * nod, st, mid, val, pana_acum);
    }
    else{
        return aint_query(2 * nod + 1, mid + 1, dr, val, pana_acum + aint[2 * nod]);
    }
}

void citire(){
    fin >> n;
    for(int i = 1; i <= n; i++){
        fin >> pozitii_relative[i];
    }
}

void procesare_pozitii(){
    int poz_real;

    for(int i = n; i >= 1; i--){
        poz_real = aint_query(1, 1, n, pozitii_relative[i], 0);
        clasament[poz_real] = i;
        aint_update(1, 1, n, poz_real);
    }
}

void afisare(){
    for(int i = 1; i <= n; i++){
        fout << clasament[i] << '\n';
    }
}

int main(){
    citire();

    aint_build(1, 1, n);
    procesare_pozitii();

    afisare();

    return 0;
}