Cod sursa(job #1004652)

Utilizator andreiiiiPopa Andrei andreiiii Data 3 octombrie 2013 14:01:11
Problema Schi Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <cstdio>
#include <algorithm>
#define N 30001
#define zeros(x) ((x)&(-x))
using namespace std;

int a[N], aib[N], sol[N];
int n;

void update(int nod, int val)
{
	for(int i=nod;i<=n;i+=zeros(i))
	{
		aib[i]+=val;
	}
}

int query(int nod)
{
	int i=nod, ret=0;
	for(i=nod;i;i-=zeros(i))
	{
		ret+=aib[i];
	}
	return ret;
}

int bs(int val)
{
	int i, step;
	for(step=1;step<=n;step<<=1);
	for(i=n;step;step>>=1)
	{
		if(i-step>0&&aib[i-step]>=val)
		{
			i-=step;
		}
	}
	return i;
}

int main()
{
	freopen("schi.in", "r", stdin);
	freopen("schi.out", "w", stdout);
	int i, poz;
	scanf("%d", &n);
	for(i=1;i<=n;i++)
	{
		scanf("%d", &a[i]);
		update(i, 1);
	}
	for(i=n;i;i--)
	{
		poz=bs(a[i]);
		sol[poz]=i;
		update(poz, -1);
	}
	for(i=1;i<=n;i++)
	{
		printf("%d\n", sol[i]);
	}
}