Cod sursa(job #749866)

Utilizator deividFlorentin Dumitru deivid Data 19 mai 2012 12:37:20
Problema Schi Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.52 kb
#include<stdio.h>
#include<cstdlib>
#include<ctime>

#define maxn 30005

FILE*f=fopen("schi.in","r");
FILE*g=fopen("schi.out","w");

int n,before;
unsigned short int poz[maxn],res[maxn];

struct node{
	unsigned short int key,priority;
	unsigned short int nrsubarb;
	node *ls,*rs;
	
	node ( unsigned short int _key , unsigned short int _priority , node *_ls , node *_rs , unsigned short int _nr ){
		key = _key; priority = _priority;
		ls = _ls; rs = _rs;
		nrsubarb = _nr;
	}
};

node *R,*nul;

inline void update ( node *&nod ){
	
	nod->nrsubarb = 1 + nod->ls->nrsubarb + nod->rs->nrsubarb;
}

inline void rotate_ls ( node *&nod ){
	
	node *fiu = nod->ls;
	nod->ls = fiu->rs;
	fiu->rs = nod;
	nod = fiu;
}

inline void rotate_rs ( node *&nod ){
	
	node *fiu = nod->rs;
	nod->rs = fiu->ls;
	fiu->ls = nod;
	nod = fiu;
}

inline void balance ( node *&nod ){
	
	if ( nod->ls->priority > nod->priority ){
		rotate_ls(nod);
	}
	else{
		if ( nod->rs->priority > nod->priority ){
			rotate_rs(nod);
		}
		else{
			update(nod);
		}
	}
}

void insert ( node *&nod , int key , int priority ){
	if ( nod == nul ){
		nod = new node(key,priority,nul,nul,1);
		return ;
	}
	
	if ( nod->key > key ){
		insert(nod->ls,key,priority);
	}
	else{
		insert(nod->rs,key,priority);
	}
	balance(nod);
}

void erase ( node *&nod , int key ){
	
	if ( nod->key > key ){
		erase(nod->ls,key);
	}
	else{
		if ( nod->key < key ){
			erase(nod->rs,key);
		}
		else{
			if ( nod->ls == nul && nod->rs == nul ){
				delete nod; nod = nul;
				return ;
			}
			else{
				if ( nod->ls->priority > nod->rs->priority ){
					rotate_ls(nod);
				}
				else{
					rotate_rs(nod);
				}
				erase(nod,key);
			}
		}
	}
	update(nod);
}

void query ( node *&nod , int nr , int &position ){
	
	if ( nod->ls->nrsubarb == nr - 1 ){
		position = nod->key;
		return ;
	}
	if ( nod->ls->nrsubarb >= nr ){
		query(nod->ls,nr,position);
	}
	else{
		nr -= (nod->ls->nrsubarb + 1);
		query(nod->rs,nr,position);
	}
}

int main () {
	
	fscanf(f,"%d",&n);
	for ( int i = 1 ; i <= n ; ++i ){
		fscanf(f,"%d",&poz[i]);
	}
	
	srand(time(NULL));
	R = nul = new node(0,0,NULL,NULL,0);
	
	for ( int i = 1 ; i <= n ; ++i ){
		insert(R,i,rand()+1);
	}
	
	for ( int i = n ; i >= 1 ; --i ){
		
		int position;
		query(R,poz[i],position);
		
		res[position] = i;
		erase(R,position);
	}
	
	for ( int i = 1 ; i <= n ; ++i ){
		fprintf(g,"%d\n",res[i]);
	}
	
	fclose(f);
	fclose(g);
	
	return 0;
}