Cod sursa(job #141952)

Utilizator alex_mircescuAlex Mircescu alex_mircescu Data 23 februarie 2008 22:10:10
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <stdio.h>
#include <math.h>

#define max 64*1024

long v[max], r[max], t[max];

long find(long a, long b, long c, long d) {
	if (b == c) {
		return b;
	}
	if (r[d * 2] >= a) {
		return find(a, b, (b + c) / 2, d * 2);
	}
	return find(a - r[d * 2], (b + c) / 2 + 1, c, d * 2 + 1);
}

void del(long a, long b, long c, long d) {
	--r[d];
	if (b == c) {
		return;
	}
	if (a <= (b + c) / 2) {
		del(a, b, (b + c) / 2,d * 2);
	} else {
		del(a, (b + c) / 2 + 1, c, d * 2 + 1);
	}
}
void newarb(long a, long b, long c) {
	r[a] = c - b + 1;
	if (b == c) {
		return;
	}
	newarb(a * 2, b, (b + c) / 2);
	newarb(a * 2 + 1, (b + c) / 2 + 1, c);
}
int main() {
	long i, n, w;
	freopen("schi.in", "r", stdin);
	freopen("schi.out", "w", stdout);
	
	scanf("%ld", &n);
	for (i = 1; i <= n; ++i)
		scanf("%ld", &v[i]);
	
	newarb(1, 1, n);
	for(i = n; i >= 1; --i) {
		w = find(v[i], 1, n, 1);
		t[w] = i;
		del(w, 1, n, 1);
	}
	for (i = 1; i <= n; ++i) {
		printf("%ld\n", t[i]);
	}

	return 0;
}