data-structure - Skip_list

// SKIP LIST
// https://www.codechef.com/JAN12/problems/CARDSHUF

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)


#define RAND (rand()/(RAND_MAX+1.0))

#define SKIPLIST_MAX_HEIGHT 18
#define SKIPLIST_SCALE 2.0

typedef struct struct_skip_list{
  int height;
  int val;
  int *dist;
  struct struct_skip_list **next;
}skipList;


void skipListInit(skipList *s, int val, int height){
  int i;
  if(height <= 0){
    REP(i,1,SKIPLIST_MAX_HEIGHT) if(RAND*SKIPLIST_SCALE < 1.0) break;
    height = i;
  }
  s->dist = (int*)malloc(height*sizeof(int));
  s->next = (skipList**)malloc(height*sizeof(skipList*));
  rep(i,height) s->dist[i] = -1;
  s->val = val;
  s->height = height;
}

void skipListFree(skipList *s){
  free(s->dist); free(s->next);
}

int skipListGetSize(skipList *s){
  int i;
  for(i=s->height-1; i>=0; i--) if(s->dist[i] > 0){
    return s->dist[i] + skipListGetSize(s->next[i]);
  }
  return 0;
}

void skipListAddElementInLast(skipList *s, skipList *add, int sz){
  int i;
  for(i=s->height-1; i>=0; i--){
    if(s->dist[i] < 0 && i < add->height){
      if(sz <= -1) sz = skipListGetSize(s);
      s->dist[i] = sz+1;
      s->next[i] = add;
      continue;
    }
    if(s->dist[i] >= 0){
      skipListAddElementInLast(s->next[i], add, sz-(s->dist[i]));
      break;
    }
  }
}

void skipListAddListInLast(skipList *s, skipList *add, int sz){
  int i;
  for(i=s->height-1; i>=0; i--){
    if(s->dist[i] < 0 && add->dist[i] >= 0){
      if(sz <= -1) sz = skipListGetSize(s);
      s->dist[i] = sz + add->dist[i];
      s->next[i] = add->next[i];
      continue;
    }
    if(s->dist[i] >= 0){
      skipListAddListInLast(s->next[i], add, sz-(s->dist[i]));
      break;
    }
  }
}

/* a => a[1..K], b => a[K+1..last] */
void skipListDevide(skipList *a, skipList *b, int K){
  int i;

  rep(i,a->height) b->dist[i] = -1;

  for(i=a->height-1; i>=0; i--){
    if(a->dist[i] < 0) continue;
    if(a->dist[i] > K){
      b->dist[i] = a->dist[i] - K;
      b->next[i] = a->next[i];
      a->dist[i] = -1;
      continue;
    }
    if(a->dist[i] <= K){
      skipListDevide(a->next[i], b, K-(a->dist[i]));
      break;
    }
  }
}

skipList* skipListGetKthElement(skipList *s, int K){
  int i;

  if(K==0) return s;
  for(i=s->height-1; i>=0; i--){
    if(s->dist[i] < 0) continue;
    if(K >= s->dist[i]) return skipListGetKthElement(s->next[i], K-(s->dist[i]));
  }

  return (skipList*)NULL;
}

void skipListPuts(skipList *s){
  int br = 0;
  for(;;){
    if(s->dist[0] < 0) break;
    s = s->next[0];
    /*    if(br) printf(" -> "); else br = 1;*/
    if(br) putchar(' '); else br = 1;
    printf("%d",s->val+1);
  }
  puts("");
}


skipList S, A, B, C, ls[111111]; /* list: 1 -> 2 -> ... initially */
skipList SS, AA, BB, CC, lsls[111111]; /* list: N -> N-1 -> ... initially */

int main(){
  int i,j,k,l;
  int N, M;
  int a, b, c;
  skipList swap;

  srand(time(NULL));

  skipListInit(&S, -1, SKIPLIST_MAX_HEIGHT);
  skipListInit(&A, -1, SKIPLIST_MAX_HEIGHT);
  skipListInit(&B, -1, SKIPLIST_MAX_HEIGHT);
  skipListInit(&C, -1, SKIPLIST_MAX_HEIGHT);
  skipListInit(&SS, -1, SKIPLIST_MAX_HEIGHT);
  skipListInit(&AA, -1, SKIPLIST_MAX_HEIGHT);
  skipListInit(&BB, -1, SKIPLIST_MAX_HEIGHT);
  skipListInit(&CC, -1, SKIPLIST_MAX_HEIGHT);

  scanf("%d%d",&N,&M);
  rep(i,N) skipListInit(ls+i, i, 0);
  rep(i,N) skipListAddElementInLast(&S, ls+i, i);
  rep(i,N) skipListInit(lsls+i, N-1-i, 0);
  rep(i,N) skipListAddElementInLast(&SS, lsls+i, i);

  while(M--){
    scanf("%d%d%d",&a,&b,&c);

    swap = S; S = A; A = swap;
    skipListDevide(&A, &S, a);
    skipListDevide(&SS, &AA, N-a);

    swap = S; S = B; B = swap;
    skipListDevide(&B, &S, b);
    skipListDevide(&SS, &BB, N-a-b);

    swap = S; S = A; A = swap;
    skipListAddListInLast(&S, &A, a);
    skipListAddListInLast(&SS, &AA, N-a-b);

    swap = S; S = C; C = swap;
    skipListDevide(&C, &S, c);
    skipListDevide(&SS, &CC, N-b-c);

    swap = S; S = BB; BB = swap;
    skipListAddListInLast(&S, &BB, b);
    skipListAddListInLast(&SS, &B, N-b-c);

    swap = S; S = C; C = swap;
    skipListAddListInLast(&S, &C, c);
    skipListAddListInLast(&SS, &CC, N-c);
  }

  skipListPuts(&S);

  return 0;
}