Cod sursa(job #685451)

Utilizator vlad.doruIon Vlad-Doru vlad.doru Data 20 februarie 2012 22:29:34
Problema Schi Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <fstream>

using namespace std;

ifstream in("schi.in");
ofstream out("schi.out");

const int N=30000;

int n,v[N],aib[N],final[N];

int suma(int poz){
	int s=0;
	s+=aib[poz];
	if(poz==0)
		return 0;
	poz-=(poz-(poz&(poz-1)));
	s+=suma(poz);
	return s;
}

void scade(int poz){
	if(poz>n)
		return;
	aib[poz]--;
	poz+=(poz-(poz&(poz-1)));
	scade(poz);
}

int extract(int x){
	int i,pas,aux;
	for(pas=1;pas<=n;pas<<=1);
	for(i=0;pas;pas>>=1){
		if(i+pas>n)
			continue;
		aux=suma(i+pas);
		if(aux<x && i+pas<=n){
			i+=pas;
			continue;
		}
		if(aux==x && i+pas<=n){
			i+=pas;
			scade(i);
			return i;
		}
	}
}

int main(){
	int i;
	in>>n;
	for(i=1;i<=n;++i){
		in>>v[i];
		aib[i]=(i-(i&(i-1)));
	}
	for(i=n;i>=1;i--){
		final[extract(v[i])]=i;
	}
	for(i=1;i<=n;++i){
		out<<final[i]<<"\n";
	}	
	return 0;
}