Pagini recente » Cod sursa (job #3362544) | Cod sursa (job #3363044) | Cod sursa (job #3362992) | Cod sursa (job #3363033) | Cod sursa (job #3362974)
#include <stdio.h>
#define MAXN 32768
int v[MAXN + 1], f[MAXN + 1], poz[MAXN + 1], arb[2 * MAXN];
int query(int n, int sum) {
int st, dr, nod, p2;
nod = p2 = st = 1;
dr = n;
while (p2 <= n) {
if (arb[2 * nod] >= sum) {
dr = (st + dr) / 2;
nod = 2 * nod;
} else {
st = (st + dr) / 2 + 1;
sum -= arb[2 * nod];
nod = 2 * nod + 1;
}
p2 *= 2;
}
return dr;
}
void update(int n, int idx, int val) {
int poz;
poz = n + idx - 1;
arb[poz] = val;
n /= 2;
while (n) {
poz = (poz - (poz & 1)) / 2;
arb[poz] = arb[2 * poz] + arb[2 * poz + 1];
n /= 2;
}
}
int main() {
FILE *fin, *fout;
int n, np2, p2, rez, i;
fin = fopen("schi.in", "r");
fscanf(fin, "%d", &n);
for (i = 1; i <= n; i++) {
fscanf(fin, "%d", &v[i]);
f[i] = 1;
}
fclose(fin);
p2 = 1;
while (p2 < n) {
p2 *= 2;
}
np2 = p2;
for (i = np2; i < 2 * np2; i++) {
arb[i] = f[i - np2 + 1];
}
p2 /= 2;
while (p2) {
for (i = p2; i < 2 * p2; i++) {
arb[i] = arb[2 * i] + arb[2 * i + 1];
}
p2 /= 2;
}
for (i = n; i >= 1; i--) {
rez = query(np2, v[i]);
printf("%d %d %d\n", i, v[i], rez);
poz[rez] = i;
update(np2, rez, 0);
}
fout = fopen("schi.out", "w");
for (i = 1; i <= n; i++) {
fprintf(fout, "%d\n", poz[i]);
}
fclose(fout);
return 0;
}