Cod sursa(job #809924)

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

using namespace std;

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

int n;
int *v=new int[30100]; // bucket[i] tine de la bucket*i pana la bucketsize*(i+1) -1 ;
int *bucket=new int[300];
int *occupied=new int[30100];
int *place=new int[30100];
int bucketsize;

int query(int x){
	int i=0;
	int sum=0;
	while(sum+bucket[i]<x && i<n/bucketsize){
		sum+=bucket[i];
		++i;
	}
	int j;
	for(j=i*bucketsize;sum!=x && j<=n;++j){
		sum+=occupied[j];
	}
	return j-1;
}

void decrement(int x){
	bucket[x/bucketsize]--;
	occupied[x]--;
}

int main(){
	in>>n;
	bucketsize=(int)sqrt(n);
	int i;
	bucket[0]=bucketsize-1;
	for(i=1;i<=n/bucketsize;++i){
		bucket[i]=bucketsize;
	}
	bucket[n/bucketsize]=n- (n/bucketsize)*bucketsize +1;
	for(i=1;i<=n;++i){
		occupied[i]=1;
		in>>v[i];
	}
	for(i=n;i>0;--i){
		place[query(v[i])]=i;
		decrement(query(v[i]));
	}
	for(i=1;i<=n;++i){
		out<<(place[i]);
	}
	return 0;
}