Cod sursa(job #775017)

Utilizator elfusFlorin Chirica elfus Data 7 august 2012 01:57:26
Problema Schi Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <stdio.h>
#define NMAX 30100

int rank[NMAX], AIB[NMAX], sol[NMAX];

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

int query(int pos)
{
	int ans = 0;
	for (; pos > 0; pos = pos - lsb(pos))
		ans += AIB[pos];
	return ans;
}

void update(int pos, int N)
{
	for (; pos <= N; pos = pos + lsb(pos))
		AIB[pos] ++;
}

inline int countFree(int x)
{
	return x - query(x);
}

int binarySearch(int left, int right, int rank)
{
	int med;
	
	while (left <= right)
	{
		med = (left + right) / 2;

		if (countFree(med) < rank)
			left = med + 1;
		else
			right = med - 1;
	}
	
	return left;
}

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