Pagini recente » Cod sursa (job #701486) | Cod sursa (job #1600110) | Cod sursa (job #2827292) | Cod sursa (job #36695) | Cod sursa (job #2560517)
/// 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;
}