Cod sursa(job #245104)

Utilizator yoyolichIoana Ardeleanu yoyolich Data 16 ianuarie 2009 20:00:37
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.84 kb
#include<stdio.h>
#include<stdlib.h>
#include<ctime>
FILE *f=fopen("order.in","r"), *g=fopen("order.out","w");
struct nod { int v,p, nrnodes; nod *l,*r;};

typedef nod* treap;
treap R,nil;

int n,i,q,k,p;
inline void init()
{
	nil=new nod;
	nil->l=nil->r=0;
	nil->v=nil->p=-0x3f3f3f3f;
	nil->nrnodes=0;
	R=nil;
}

inline void geth(treap &n)
{
	if(n == nil) return;
	n->nrnodes=n->l->nrnodes + n->r->nrnodes +1;
}

inline void rotleft(treap &n)
{
	treap t=n->l;
	n->l=t->r;
	t->r=n;
	geth(n); geth(t); 
	n=t;
}

inline void rotright(treap &n)
{
	treap t=n->r;
	n->r=t->l;
	t->l=n;
	geth(n); geth(t); 
 	n=t;
}
	
inline void insert(treap &n, int v)
{
	if(n == nil) 
	{
		n=new nod;
		n->l=n->r=nil;
		n->v=v;
		n->nrnodes=1;
		n->p=rand();
		return ;
	}
	
	if(v < n->v)
	{
		insert(n->l, v);
		if(n->l->p > n->p) rotleft(n);
	}
	
	if(v > n->v)
	{
		insert(n->r, v);
		if(n->r->p > n->p) rotright(n);
	}
	geth(n); 
}


inline void sterge(treap &n, int v)
{
	if(n == nil) return;
	if(v < n->v) sterge(n->l, v);
	if(v > n->v) sterge(n->r, v);
	if(v == n->v)
	{
		if(n->l == nil && n->r == nil) 
		{
			delete n;
			n=nil;
			return;
		}
		
		if(n->l->p  > n->r->p) rotleft(n); 
		else rotright(n);
		
		sterge(n, v);
	}
	geth(n);
}

inline int findk(treap n, int k)
{
	if(n == nil) return 0;
	if(n->l->nrnodes + 1 == k) return n->v;
	if(n->l->nrnodes + 1 > k) return findk(n->l, k);
	else return findk(n->r, k - (n->l->nrnodes+1));
	return 0;
}

int main()
{
	fscanf(f,"%d",&n);
	fclose(f);
	
	init();
	for(i=1;i<=n;i++) insert(R,i);
	p=1;
	i=1;
	k=1;
	while(n)
	{
		p+=k;
		p%=n;
		if(i!=1) p--;
		if(p==-1) p=n-1;  
		if(p==0) p=n;
		k++;
		q=findk(R,p);
		fprintf(g,"%d ",q);
		sterge(R,q);
		++i;
		n--;
	}
		
	
	fprintf(g,"\n");
	fclose(g);
	return 0;
}