Cod sursa(job #808561)

Utilizator vlad.doruIon Vlad-Doru vlad.doru Data 6 noiembrie 2012 22:04:58
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <fstream>

using namespace std;

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

const int N=30100;

int aib[N];
int v[N];
int position[N];
int n;

void add(int x,int pos){
	if(pos>n){
		return;
	}
	aib[pos]+=x;
	pos+=(pos-(pos&(pos-1)));
	add(x,pos);
}

int query(int pos){
	int result=0;
	while(pos){
		result+=aib[pos];
		pos-=(pos-(pos&(pos-1)));
	}
	return result;
}

int finalplace(int x){
	int i,step,min;
	for(step=1;step<=n;step<<=1);
	for(i=0;step;step>>=1){
		if(i+step<=n && query(i+step)<x){
			i+=step;
			continue;
		}
		if( i+step<=n && query(i+step)==x){
			min=i+step; // ne trebuie minimul
			continue;
		}
	}
	return min;
}

int main(){
	int i,place;
	in>>n;
	for(i=1;i<=n;++i){
		add(1,i);
		in>>v[i];
	}
	for(i=n;i>=1;--i){
		place=finalplace(v[i]);
		position[place]=i;
		add(-1,place);
	}
	for(i=1;i<=n;++i){
		out<<position[i]<<"\n";
	}
}