Cod sursa(job #1259937)

Utilizator killer301Ioan Andrei Nicolae killer301 Data 10 noiembrie 2014 18:37:03
Problema Schi Scor 75
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#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;
}