Cod sursa(job #400698)

Utilizator APOCALYPTODragos APOCALYPTO Data 21 februarie 2010 20:28:49
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.32 kb
#include<iostream>
#include<fstream>
#include<cstdlib>
#include<vector>
#define oo 0x3f3f3f3f //infinit
using namespace std;

  struct nod{
      int v,p,sub;
      nod *r,*l;
      };
typedef nod* treap;
treap R,nil;
ofstream fout("order.out");
ifstream fin("order.in");


inline void init()
{ nil=new nod;
nil->v=nil->p=-oo;
nil->sub=0;
nil->l=nil;
nil->r=nil;
R=nil;
}
inline void getsub(treap&n)
{if(n==nil) return;
n->sub=1;
if(n->l!=nil) n->sub+=n->l->sub;
if(n->r!=nil) n->sub+=n->r->sub;

}
void rright(treap &n)
{treap t=n->r;
n->r=t->l;
t->l=n;
getsub(n);
getsub(t);
n=t;
}

void rleft(treap &n)
{treap t=n->l;
n->l=t->r;
t->r=n;
getsub(n);
getsub(t);
n=t;
}
void insert(treap &n,int v)
{if(n==nil)
{n=new nod;
n->l=n->r=nil;
n->v=v;
n->sub=1;
n->p=rand()-1;
return;
}
if(n->v <v)
   {insert(n->r,v);
   if(n->r->p > n->p)
      rright(n);
   }
if(n->v >v)
  {insert(n->l,v);
  if(n->l->p > n->p)
    rleft(n);
  }
  getsub(n);
}

void sterge(treap &n,int v)
{
if(n==nil) return;
if(n->v < v) sterge(n->r,v);
if(n->v > v) sterge(n->l,v);
if(n->v==v)
{
    if(n->l==nil && n->r==nil)
    {
        delete n;
        n=nil;
        return;
    }
    else
    if(n->l->p > n->r->p)
        rleft(n);
        else
        rright(n);
    sterge(n,v);
}
getsub(n);
}

int fiind(treap &n,int k)                         /// nu stiu de ce nu merge asta:-?? ca daca avem 1 2 3  ar trebui sa mearga
{if(n==nil) return 0;
if(k==n->sub) return n->v;
if(k<n->sub) return fiind(n->l,k);
if(k>n->sub) return fiind(n->r,k-(n->sub));
return 0;
}
inline int findk(treap n, int k)                ///
{
  if(n==nil) return 0;
  if(k==n->l->sub+1) return n->v;
  if(k<n->l->sub+1) return findk(n->l, k);
  else return findk(n->r, k-(n->l->sub+1));
  return 0;
}

int main()
{ int namb,i,k,p,fifi;
      srand(time(0));
    init();

    ifstream fin("order.in");
     fin>>namb;
     fin.close();
     for(i=1;i<=namb;i++)
      insert(R,i);
     p=1;
     k=1;
     while(namb)
     {p=((p+k)-1)%namb+1; // pentru ca astfel restul va fi mereu in range-ul [1...NAMB]=> great succes !!!:D

     fifi=findk(R,p);
     fout<<fifi<<" ";
     sterge(R,fifi);
     k++;
     namb--;
     p=p-1;
     }

fin.close();
fout.close();




    return 0;
}