Cod sursa(job #2560517)

Utilizator mariusn01Marius Nicoli mariusn01 Data 28 februarie 2020 08:25:29
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.58 kb
/// am un vector de frecventa cu n elemente, toate cu valoarea 1
/// parcurg schiorii descrescator si la cel curent pozitia sa reala
/// in clasament este egala cu pozitia pe care se afla al C[i]-lea 1
/// numarand in vecrtorul de frecventa de la stanga la dreapta.
/// apoi 1 de pe acea pozitie il facem 0.

/// simulez asta cu un arbore de intervale care are in fiecare interval
/// numarul de valori 1 din acel interval.

#include <fstream>
#define DIM 30001

using namespace std;

int C[DIM],L[DIM];
int V[DIM*3];

int n,i;

/// construiesc aint cu 1 peste tot, deci in fiecare interval
/// initial este ca valoare chiar lungimea intervalului
void cre(int st, int dr, int nod){
    int mij;
    if (st==dr){
        V[nod] = 1;
    }
    else{
        mij = (st+dr)/2;
        cre(st, mij, 2*nod);
        cre(mij+1, dr, 2*nod+1);
        V[nod] = V[2*nod]+V[2*nod+1];
    }
}

void cautSiCorect(int st, int dr, int nod, int c, int poz){
    int mij;
    if (st==dr){
        V[nod] = 0;
        L[st] = c;
    }
    else{
        mij = (st+dr)/2;
        if (V[2*nod]>=poz)
            cautSiCorect(st,mij,2*nod,c,poz);
        else
            cautSiCorect(mij+1,dr,2*nod+1,c,poz-V[2*nod]);
        V[nod] = V[2*nod]+V[2*nod+1];
    }
}

int main(){
    ifstream fin("schi.in");
    ofstream fout("schi.out");
    fin>>n;
    for (i=1; i<=n; i++){
        fin>>C[i];
    }

    cre(1,n,1);

    for (i=n; i>=1; i--){
        cautSiCorect(1,n,1,i,C[i]);
    }


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

    return 0;
}