Seletiva IOI 2013

codreverso.cpp

// Ivan Carvalho
// Código Reverso - Seletiva IOI - OBI 2013
#include <bits/stdc++.h>
#define MAXN 500001
#define LSOne(S) (S&(-S))
int n,bit[MAXN],vetor[MAXN],exibir[MAXN];
void update(int pos, int val){
	while(pos <= n){
		bit[pos] += val;
		pos += LSOne(pos);
	}
}
int sum(int pos){
	int answer = 0;
	while(pos > 0){
		answer += bit[pos];
		pos -= LSOne(pos);
	}
	return answer;
}
int find(int val){
	int ini = 1 , fim = n, meio,resp;
	while(ini <= fim){
		meio = (ini+fim)/2;
		int soma = sum(meio);
		//printf("INI: %d MEIO: %d FIM: %d SOMA: %d VAL: %d\n",ini,meio,fim,soma,val);
		if (soma >= val){
			resp = meio;
			fim = meio - 1;
		}
		else ini = meio + 1;
	}
	return resp;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		update(i,1);
		scanf("%d",&vetor[i]);
	}
	for(int i=n;i>0;i--){
		int k = i - vetor[i];
		exibir[i] = find(k);
		update(exibir[i],-1);
	}
	for(int i=1;i<=n;i++) printf("%d ",exibir[i]);
	printf("\n");
	return 0;
	return 0;
}