Cod sursa(job #3289450)

Utilizator mihai_bosIancu Mihai mihai_bos Data 26 martie 2025 21:33:17
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <fstream>

using namespace std;

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

const int NMAX = 30000;
int aint[4*NMAX], n, v[NMAX], i, sol[NMAX];

void build(int nod, int st, int dr) {
    if(st == dr)
        aint[nod] = 1;
    else {
        int mij = (st + dr) / 2;
        build(2*nod, st, mij);
        build(2*nod+1, mij+1,dr);
        aint[nod] = aint[2*nod] + aint[2*nod+1];
    }
}

int query(int nod, int st, int dr, int x){
    if(st == dr)
        return st;
    int mij = (st + dr) / 2;
    if(x <= aint[2*nod])
        return query(2*nod, st, mij, x);
    else
        return query(2*nod+1, mij+1,dr, x - aint[2*nod]);

}

void update(int nod, int st, int dr, int poz) {
    if(st == dr)
        aint[nod] = 0;
    else {
        int mij = (st + dr) / 2;
        if(poz <= mij)
            update(2*nod, st, mij, poz);
        else
            update(2*nod+1, mij+1, dr, poz);
        aint[nod] = aint[2*nod] + aint[2*nod+1];
    }
}

int main()
{
    in >> n;
    for(i = 1; i <= n; ++i)
        in >> v[i];
    build(1,1,n);
    for(i = n; i >= 1; --i) {
        int poz = query(1,1,n,v[i]);
        sol[poz] = i;
        update(1,1,n,poz);
    }
    for(i = 1; i <= n; ++i)
        out << sol[i] << '\n';

    return 0;
}