Cod sursa(job #222194)

Utilizator mika17Mihai Alex Ionescu mika17 Data 21 noiembrie 2008 01:26:46
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.66 kb
#include <cstdio>
#include <cstdlib>
#include <ctime>

#define MAX_BUF_SIZE 500000

class euroTreap {

        public:

        struct node {

        int data,ord,prio;    /* ord(p)=nr fii ai lui p +1 */
        node *l ,*r;

        node(int data1,int ord1,int prio1,node * l1,node * r1) :
          data(data1), ord(ord1), prio(prio1), l(l1), r(r1) {}
        };

        node *root, *NIL;

        euroTreap()
        {
         srand(time(NULL));
         root = NIL = new node(0,0,-1,NULL,NULL);
        }

        inline int size()
        {
         return root->ord;
        }

        inline int getord(node *p)
        {
         return p->l->ord + p->r->ord + 1;
        }

        node * left(node *p)
        {
         node *t = p->r;
         p->r = t->l;
         t->l = p;
         p->ord = getord(p), t->ord = getord(t);
         return t;
        }

        node * right(node *p)
        {
         node *t = p->l;
         p->l = t->r;
         t->r = p;
         p->ord = getord(p), t->ord = getord(t);
         return t;
        }

        node * insert(node *p,int val)
        {
         if(p == NIL)
         {
          return new node(val,1,rand(),NIL,NIL);
         }
         
         else
         {
          if(val < p->data)
          {
           p->l = insert(p->l,val);
           p->ord = getord(p);
           if(p->prio < p->l->prio)
            p = right(p);  //rotatie dr
          }
          
          else
           
            if(val > p->data)       /* nu permite duplicate */
            {
             p->r = insert(p->r,val);
             p->ord = getord(p);
             if(p->prio < p->r->prio)
              p = left(p); //rotatie st
            }

          return p;
         }
        }

        node * erase(node *p,int kth)   /* sterge al k-lea element */
        {
         if(p->ord == 1) /* subarbori vizi */
         {
          delete p;
          return NIL;
         }
          else
          {
           if(kth == p->l->ord + 1) /* am gasit al k-lea element */
           {
            if(p->l->prio > p->r->prio)
             p = erase(right(p),p->l->ord + 1) ;
            else p = erase(left(p),p->l->ord + 1);
           }
           else
            if(kth < p->l->ord + 1)
              p->l = erase(p->l,kth);
             else p->r = erase(p->r,kth - p->l->ord - 1);

           p->ord = getord(p);

           return p;
          }
        }

        int search(node *p,int kth)
        {
         if(p == NIL) return -1;
         if(p->l->ord + 1 == kth) return p->data;
          else
           if(kth < p->l->ord + 1) return search(p->l,kth);
             else
              return search(p->r,kth - p->l->ord - 1);
        }

        void debug(node *p)
        {
         if(p != NIL) {
         debug(p->l);

         printf("DATA = %d  ORD = %d  PRIO = %d  LEFT = %d RIGHT = %d\n",
         p->data,p->ord,p->prio,p->l->data,p->r->data);


         debug(p->r);
         }
        }
        
};

int main() {

        int N;

        freopen("order.in","r",stdin);
        freopen("order.out","w",stdout);

        char buf[MAX_BUF_SIZE];
        setbuf(stdout,buf);

        euroTreap *trp = new euroTreap();

        scanf("%d",&N);

        for(int i = 1; i <= N; ++i)
        {
         trp->root = trp->insert(trp->root,i);
        }

        for(int kth = 2,i = 1;i <= N; ++i)
        {
         kth = (kth = (kth - 1 + i) % trp->size()) ? kth : trp->size() ;

         printf("%d ",trp->search(trp->root,kth));

         trp->root = trp->erase(trp->root,kth);
        }
        return 0;
}