Cod sursa(job #854498)

Utilizator krissu93FMI Tiugan Cristiana Elena krissu93 Data 13 ianuarie 2013 17:52:38
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <fstream>
#include <iostream>
#define nmax 30009

using namespace std; 

ifstream in("schi.in");
ofstream out("schi.out");
int v[nmax];
int clas[nmax];
int n;
int arb[70000];

void refresh(int nod, int st, int dr,int poz, int val)
{
	if (st==dr) arb[nod]=val;
	else{
		int mij=(st+dr)/2;
		int fs=2*nod;
		int fd=2*nod+1;
		if (poz<=mij) refresh(fs,st,mij,poz,val);
		else refresh(fd,mij+1,dr,poz,val);
		arb[nod]=arb[fs]+arb[fd];
	}
}

int find (int nod, int st, int dr,int val){
	if (st==dr) return st;
	else{
		int mij=(st+dr)/2;
		int fs=2*nod;
		int fd=2*nod+1;
		if (val<=arb[fs]) return find(fs,st,mij,val);
		else return find(fd,mij+1,dr,val-arb[fs]);
	}
}
int main(){
	in>>n;
	int poz;
	for (poz=1;poz<=n;poz++){
		refresh(1,1,n,poz,1);
		in>>v[poz];
	}
	for (int i=n;i>0;i--){
		poz=find(1,1,n,v[i]);
		clas[poz]=i;
		refresh(1,1,n,poz,0);
	}
	for (int i=1;i<=n;i++){
		out<<clas[i]<<'\n';
	}
	return 0;
}