Cod sursa(job #1266925)

Utilizator killer301Ioan Andrei Nicolae killer301 Data 19 noiembrie 2014 12:03:23
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.34 kb
//75 pct O(n*log^2 n)
/*#include <cstdio>

using namespace std;

const int nmax=30000;

int n, ans;
int a[nmax+5];
int arbint[4*nmax+1];
int sol[nmax+5];

void update(int nod, int st, int dr, int poz, int val)
{
    if(st==dr)arbint[nod]=val;
    else
    {
        int mid=(st+dr)/2;
        if(poz<=mid)update(2*nod, st, mid, poz, val);
        else update(2*nod+1, mid+1, dr, poz, val);
        arbint[nod]=arbint[2*nod]+arbint[2*nod+1];
    }
}

void querry(int nod, int st, int dr, int x, int y)
{
    int mid=(st+dr)/2;
    if(st>=x && y>=dr)
    {
        ans+=arbint[nod];
        return;
    }
    mid=(st+dr)/2;
    if(x<=mid)querry(2*nod, st, mid, x, y);
    if(y>mid)querry(2*nod+1, mid+1, dr, x, y);
}

int binary(int i)
{
	int st=i, dr=n;
	while(st<=dr)
	{
		int mid=(st+dr)/2;
		ans=0;
		querry(1, 1, n, 1, mid);
		if(mid-i<ans)
			st=mid+1;
		else if(mid-i>ans)
			dr=mid-1;
		else if(mid-i==ans)
		{
			if(sol[mid]>0)
				dr=mid-1;
			else return mid;
		}
	}
}

int main()
{
    freopen("schi.in", "r", stdin);
    freopen("schi.out", "w", stdout);
    scanf("%d", &n);
    for(int i=1;i<=n;i++)
		scanf("%d", &a[i]);
	for(int i=n;i>0;i--)
	{
		int place=binary(a[i]);
		sol[place]=i;
		update(1, 1, n, place, 1);
	}
	for(int i=1;i<=n;i++)
		printf("%d\n", sol[i]);
    return 0;
}*/
#include <cstdio>

using namespace std;

const int nmax=30000;

int n;
int a[nmax+5];
int aib[4*nmax+1];
int sol[nmax+5];

inline int lsb(int x)
{
	return x & -x;
}

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

int querry(int pos)
{
	int ans=0;
	for(int i=pos; i>0; i-=lsb(i))
		ans+=aib[i];
	return ans;
}

int binary(int k)
{
	int last;
	int ans=0, sc=0;
	for(int i=1<<15; i>0; i>>=1)
		if(ans+i<=n)
		{
			int pos=ans+i;
			int query_pos=sc+aib[pos];
			if(pos - query_pos < k)
			{
				ans+=i;
				sc+=aib[ans];
			}
			else if(pos - query_pos == k)
			{
				last=ans+i;
			}
		}
	return last;
}

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