Cod sursa(job #1265164)

Utilizator stefan.friptuPetru Stefan Friptu stefan.friptu Data 16 noiembrie 2014 20:26:27
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <cstdio>

using namespace std;

const long nmax=30007;

long aib[nmax],a[nmax],ans[nmax],n,i;

void update (long poz, long val)
{
	for(;poz<=n;poz+=poz&(poz-1)^poz)
		aib[poz]+=val;
}

long query (long poz){
	long sum=0;
	for(;poz>0;poz-=poz&(poz-1)^poz)
		sum+=aib[poz];
	return sum;
}

long binary_search (long val)
{
	int st=1,dr=n;
    while(st<=dr){
        int med=(st+dr)>>1;
        if(val<=query(med))
            dr=med-1;
        else
            st=med+1;
    }
    return st;
}

int main () {

	freopen("schi.in","r",stdin);
	freopen("schi.out","w",stdout);
	
	scanf("%ld",&n);
	
	for(i=1;i<=n;i++)
	{
		scanf("%ld",&a[i]);
		update(i,1);
	}
	
	for(i=n;i>=1;i--)
	{
		long poz;
		poz=binary_search(a[i]);
		ans[poz]=i;
		update(poz,-1);
	}
	for(i=1;i<=n;i++)
		printf("%ld\n",ans[i]);
	
	
	return 0;
}