Cod sursa(job #1266058)

Utilizator AndreeaBaltaBalta Andreea Cristina AndreeaBalta Data 18 noiembrie 2014 09:51:22
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <cstdio>

using namespace std;

int aib[30005], a[30005], answer[30005], n;

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

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

int query(int b)
{
	int s = 0;
	for(;b; b -= lsb(b))
		s+= aib[b];
	return s;
}

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

int main () {

    FILE *in, *out;
    in = fopen("schi.in", "r");
    out = fopen("schi.out", "w");
    register int i;
    int poz;
    fscanf(in, "%d", &n);
    for(i = 1;i <= n; i++)
    {
        fscanf(in, "%d", &a[i]);
        update(i,1);
    }

    for(i = n;i >= 1; i--)
    {
        poz = bs(a[i]);
        answer[poz] = i;
        update(poz, -1);
    }
    for(i = 1;i <= n; i++)
        fprintf(out, "%d\n", answer[i]);
    return 0;
}