Cod sursa(job #809975)

Utilizator vlad.doruIon Vlad-Doru vlad.doru Data 9 noiembrie 2012 13:45:58
Problema Schi Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <fstream>
#include <cmath>

using namespace std;

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



int main(){
	in>>n;
	bucketsize=128;
	short int i;
	short int k=0;
	short int sum=0;
	short int j;
	short int n;
short int v[30010]; // bucket[i] tine de la bucket*i pana la bucketsize*(i+1) -1 ;
short int bucket[30010];
short int occupied[30010];
short int place[30010];
int bucketsize;
	bucket[0]=bucketsize-1;
	short int x;
	short int poz;
	short int max1=n/bucketsize;
	for(i=1;i<=max1;++i){
		bucket[i]=bucketsize;
	}
	bucket[max1]=n- max1*bucketsize +1;
	for(i=1;i<=n;++i){
		occupied[i]=1;
		in>>v[i];
	}
	for(i=n;i>0;--i){
		//query(v[i],i);
		x=v[i];
		poz=i;
		k=0;
		sum=0;
		while(sum+bucket[k]<x){
			sum+=bucket[k];
			++k;
		}
		for(j=k*bucketsize;sum!=x;++j){
			sum+=occupied[j];
		}
		--bucket[(j-1)/bucketsize];
		occupied[j-1]>>=1;
		place[j-1]=poz;
	}
	for(i=1;i<=n;++i){
		out<<place[i]<<"\n";
	}
	return 0;
}