Cod sursa(job #679556)

Utilizator BarracudaFMI-Alex Dobrin Barracuda Data 13 februarie 2012 14:27:39
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include<fstream>
#define lim 30002
using namespace std;
ifstream f("schi.in");
ofstream g("schi.out");
int arb[3*lim],s[lim],n,i,j,pos,val,v[lim],cont;
void update (int nod,int l,int s,int val){
	if(l==s){
		arb[nod]=val;
	}
	else{
		int mij=(l+s)/2;
		if(pos<=mij)
			update(2*nod,l,mij,val);
		else
			update(2*nod+1,mij+1,s,val);
		arb[nod]=arb[2*nod]+arb[2*nod+1];
	}
}
int query(int nod,int l,int s,int val){
	if(l==s)
		return s;
	else{
		int mij=(l+s)/2;
		if(val<=arb[2*nod])
			return query(2*nod,l,mij,val);
		else
			return query(2*nod+1,mij+1,s,val-arb[2*nod]);
	}
}
int main (){
	f>>n;
	for(i=1;i<=n;i++){
		f>>v[i];
	}
	for(pos=1;pos<=n;pos++)
		update(1,1,n,1);
	for(i=n;i>=1;i--){
		cont=query(1,1,n,v[i]);
		s[cont]=i;
		pos=cont;
		update(1,1,n,0);
	}
	for(i=1;i<=n;i++)
		g<<s[i]<<"\n";
	return 0;
}