Cod sursa(job #761535)

Utilizator vendettaSalajan Razvan vendetta Data 26 iunie 2012 13:56:13
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 kb
#include <iostream>
#include <fstream>

using namespace std;

#define nmax 30005

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

int n, a[nmax], rez[nmax];
int arb[nmax*4];

void citeste(){

    f >> n;
    for(int i=1; i<=n; i++) f >> a[i];

}

void udpate(int nod, int st, int dr, int poz){

    if (st == dr){
        arb[nod] = 1;
        return;
    }

    int mij = (st + dr) / 2;
    if (poz <= mij) udpate(nod*2, st, mij, poz);
        else udpate(nod*2+1, mij+1, dr, poz);

    arb[nod] = arb[nod*2] + arb[nod*2+1];

}

int afla_pozitie(int nod, int st, int dr, int val){

    if (st == dr){
        return st;
    }

    int mij = (st + dr) / 2;

    int nr = mij - st + 1 - arb[nod*2];//nr = numarul de numere nesterse din intervalul [st,mij];
    if ( nr >= val ){//daca pozitia cautata se afla in acest interval
            return afla_pozitie(nod*2, st, mij, val);
    }else{//se afla in celalat interval
            val = val - nr;//pozitia cautata va fi pozitia cautat - numarul de numere din intervalul stang(unde nu se afla pozitia cautata)
            return afla_pozitie(nod*2+1, mij+1, dr, val);
    }

}

void rezolva(){

    for(int i=n; i; i--){
        int x = a[i];
        int poz_final = afla_pozitie(1,1,n,x);
        udpate(1,1,n,poz_final);//actualizez pozitia i ca si stearsa;
        rez[poz_final] = i;
    }

    for(int i=1; i<=n; i++) g << rez[i] << "\n";

}

int main(){

    citeste();
    rezolva();

    f.close();
    g.close();

    return 0;

}