Cod sursa(job #484425)

Utilizator MKLOLDragos Ristache MKLOL Data 14 septembrie 2010 11:16:41
Problema Schi Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include<stdio.h>
int AIB[50000];
int v[50505],l[50505],N;
int zeros(int x)
{
return ((x ^ (x - 1)) & x );
}
 
void Add(int x, int quantity)
{
    int i;

    for (i = x; i <= N; i += zeros(i))
        AIB[i] += quantity;
}
void del(int x, int quantity)
{
    int i;

    for (i = x; i <= N; i += zeros(i))
        AIB[i] -= quantity;
}
int comp(int x)
{
    int i, ret = 0;

    for (i = x; i > 0; i -= zeros(i))
        ret += AIB[i];
    return ret;
}

int st,dr,mij,rez;
int main()
{
	freopen("schi.in","r",stdin);
	freopen("schi.out","w",stdout);
	scanf("%d",&N);
	for(int i=1;i<=N;++i)
		{
		scanf("%d",&v[i]);
		Add(i,1);
		}
	
	for(int i=N;i>=1;--i)
	{
		st=1;
		dr=N;
		rez=0;
		while(st<=dr)
		{
			mij=(st+dr)/2;
			//printf("%d!\n",comp(mij));
			if(comp(mij)>v[i])
				{
				dr=mij-1;
				}
			else if(comp(mij)==v[i])
			{
				rez=mij;
				dr=mij-1;
			}
			else
				st=mij+1;
		}
		l[rez]=i;
		del(rez,1);
	}
	for(int i=1;i<=N;++i)
		printf("%d\n",l[i]);
}