Nu aveti permisiuni pentru a descarca fisierul grader_test6.in

Cod sursa(job #88677)

Utilizator gigi_becaliGigi Becali gigi_becali Data 3 octombrie 2007 14:15:03
Problema Cutii Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.41 kb
#include <cstdio>
#include <string>
#include <cstdlib>
#define oo 0x3f3f3f3f



struct nod { int v, p, h; nod *l, *r;};

nod *R,*nil;
typedef nod*  treap;
inline void init()
{
  srand(time(0));
  nil=new nod;
  nil->v=nil->p=-oo;
  nil->h=0;
  nil->l=nil->r=nil;
  R=nil;
}

inline void geth(treap &n)
{
  if(n==nil)return;
  n->h=n->l->h+n->r->h+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 rotl(treap &n)
{
  treap t=n->l; n->l=t->r; t->r=n; n=t;
}

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


inline void insrt(treap &n, int v)
{
  if(n==nil)
    {
      n=new nod;
      n->v=v; n->p=rand()-1; n->h=1; n->l=n->r=nil;
      return ;
    }
 

  if(v<n->v)
    {
      insrt(n->l, v);
      if(n->l->p > n->p) rotleft(n);
    }
  if(v>n->v)
    {
      insrt(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->p > n->r->p) rotl(n);
      else rotr(n);

      if(n!=nil) sterge(n, v);
      else 
	{
	  free(n->l);
	  n->l=0;
	  
	}
    }
    geth(n);

}

void recomputeh(treap &n, int v)
{
  if(n==nil) return;
  if(v<n->v) recomputeh(n->l, v);
  else recomputeh(n->r, v);
  geth(n);
}


void ino(treap n)
{
  if(n==nil) return;
  ino(n->l);
  printf("(%d %d)   ", n->v, n->h);
  ino(n->r);
}

inline int findk(treap n, int k)
{
  if(n==nil) return 0;
  if(k==n->l->h+1) return n->v;
  if(k<n->l->h+1) return findk(n->l, k);
  else return findk(n->r, k-(n->l->h+1));
  return 0;
}
inline void del(int v)
{
  sterge(R, v);
  //recomputeh(R, v);
}

inline void insert(int v)
{
  insrt(R, v);
}

 

int main()
{
  init();
  
  int i,n, K, p=0, found;
  //se citesc n si K
  n=100000; K=100000;
  //freopen("cerc.in","r",stdin);
  freopen("cerc.out","w",stdout);
  scanf("%d %d", &n, &K);
 for(i=1;i<=n;++i)insert(i);
  i=1;
  while(n)
    {
      p+=K;
      p%=n;
      if(i!=1)--p;
      if(p==-1) p=n-1;
      if(p==0) p=n;
	  found=findk(R, p);
      printf("%d\n", found);
      del(found);
      ++i;
      --n;
    }

  return 0;
}