Cod sursa(job #35731)

Utilizator damaDamaschin Mihai dama Data 22 martie 2007 13:42:24
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.72 kb
#include <stdio.h>

int aib[32768], n, sol[32768], a[32768], p[32768];


void add(int pos);
int query(int pos);

int main()
{
	freopen("schi.in","r",stdin);
	freopen("schi.out","w",stdout);

	int i, temp;

	scanf("%d", &n);

	for(i = 1; i <= n; ++i)
	{
		scanf("%d", &a[i]);
	}
	for(i = n; i >= 1; --i)
	{
		temp = a[i] + query(a[i]);
		while(sol[i] != temp)
		{
			sol[i] = temp;
			temp = a[i] + query(temp);
		}
		add(sol[i]);
		p[sol[i]] = i;
	}
	for(i = 1; i <= n; ++i)
	{
		printf("%d\n", p[i]);
	}

	return 0;
}

void add(int pos)
{
	while(pos <= n)
	{
		++aib[pos];
		pos += pos & (pos ^ (pos - 1));
	}
}

int query(int pos)
{
	int rez = 0;

	while(pos)
	{
		rez += aib[pos];
		pos -= pos & (pos ^ (pos - 1));
	}
	return rez;
}