Pagini recente » Cod sursa (job #2300708) | Cod sursa (job #2544464) | Cod sursa (job #1124986) | Cod sursa (job #2660250) | Cod sursa (job #761535)
Cod sursa(job #761535)
#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;
}