Pagini recente » Cod sursa (job #880862) | Cod sursa (job #1057107) | Cod sursa (job #1397456) | Cod sursa (job #1070229) | Cod sursa (job #2521030)
/**
varianta cu arbori de intervale
#include <iostream>
#include <cstdio>
#define NMAX 30000
using namespace std;
int n;
int v[NMAX + 5], aint[4 * NMAX + 5], ord[NMAX + 5];
void init(int nod, int st, int dr) {
int mij = (st + dr) / 2;
aint[nod] = dr - st + 1;
if(dr != st) {
init(2 * nod, st, mij);
init(2 * nod + 1, mij + 1, dr);
}
}
int query(int nod, int st, int dr, int qval) {
int mij = (st + dr) / 2;
aint[nod]--; /// update
if(st == dr)
return st;
if(qval <= aint[2 * nod])
return query(2 * nod, st, mij, qval);
return query(2 * nod + 1, mij + 1, dr, qval - aint[2 * nod]);
}
int main() {
freopen("schi.in", "r", stdin);
freopen("schi.out", "w", stdout);
int poz;
scanf("%d", &n);
for(int i = 1; i <= n; i++)
scanf("%d", &v[i]);
init(1, 1, n);
for(int i = n; i >= 1; i--) {
poz = query(1, 1, n, v[i]);
ord[poz] = i;
}
for(int i = 1; i <= n; i++)
printf("%d\n", ord[i]);
return 0;
}
**/
/// varianta cu arbori indexati binar
#include <iostream>
#include <cstdio>
#define NMAX 30000
using namespace std;
int n, maxn;
int v[NMAX + 5], aib[NMAX + 5], ord[NMAX + 5];
int lsb(int x) {
return x & (-x);
}
int p2(int x) {
return (x - lsb(x)) == 0;
}
void init() {
int ni;
maxn = n;
while(!p2(maxn))
maxn += lsb(maxn);
for(int i = 1; i <= maxn; i++) {
if(i <= n)
aib[i]++;
ni = i + lsb(i);
aib[ni] += aib[i];
}
}
int query(int nod, int val) {
int b = lsb(nod), nnod = nod - b;
b >>= 1;
while(b) {
nnod += b;
if(val <= aib[nnod])
return query(nnod, val);
val -= aib[nnod];
b >>= 1;
}
return nod;
}
void update(int poz) {
aib[poz]--;
poz += lsb(poz);
if(poz <= maxn)
update(poz);
}
int main() {
freopen("schi.in", "r", stdin);
freopen("schi.out", "w", stdout);
int poz;
scanf("%d", &n);
for(int i = 1; i <= n; i++)
scanf("%d", &v[i]);
init();
for(int i = n; i >= 1; i--) {
poz = query(maxn, v[i]);
ord[poz] = i;
update(poz);
}
for(int i = 1; i <= n; i++)
printf("%d\n", ord[i]);
return 0;
}