Cod sursa(job #141873)

Utilizator alex_mircescuAlex Mircescu alex_mircescu Data 23 februarie 2008 20:02:41
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include<stdio.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, x;
	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);
	}
	x = n % 2 + 1;
	for(i = 1;i <= n; ++i) {
		printf("%ld\n", t[i] * x);
	}

	return 0;
}