AOC 1

1.c

/**
        0.00 real         0.00 user         0.00 sys
             1277952  maximum resident set size
                   0  average shared memory size
                   0  average unshared data size
                   0  average unshared stack size
                 191  page reclaims
                  10  page faults
                   0  swaps
                   0  block input operations
                   0  block output operations
                   0  messages sent
                   0  messages received
                   0  signals received
                   2  voluntary context switches
                  10  involuntary context switches
            13317870  instructions retired
             9271918  cycles elapsed
             1082112  peak memory footprint
**/


#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

// Binary tree
typedef struct heap {
  int b[4096];
  size_t n;
} heap;

void swap(int*,int*);
void restore_up(heap*,size_t);
void restore_down(heap*,size_t);

// Global, zero initialized
heap g_a = {.n = 1,}, g_b = {.n = 1,};

// Push a new value into the heap
void push(int v, heap* p)
{
  p->b[p->n] = v;
  restore_up(p, p->n);
  p->n++;
}

// Retreive the smallest value from the heap
int min(heap* p)
{
  if (1 == p->n) return -1;
  int v = p->b[1];
  p->b[1] = p->b[--p->n];
  restore_down(p, 1);
  return v;
}

void swap(int *a, int *b)
{
  *a = *a + *b; *b = *a - *b; *a = *a - *b;
}

// Restore heap order for newly inserted element
void restore_up(heap* p, size_t i)
{
  if (1 == i) return;
  if (p->b[i] < p->b[i/2])
  {
    swap(p->b+i, p->b+(i/2));
  }
  return restore_up(p, i/2);
}

void restore_down(heap* p, size_t i)
{
  if (2*i < p->n)
  {
    size_t x = 2*i, y = (x+1 < p->n ? x+1 : x);
    if (p->b[x] < p->b[i] && p->b[x] < p->b[y])
    {
      swap(p->b+x, p->b+i);
      restore_down(p, x);
    }
    else if (p->b[y] < p->b[i])
    {
      swap(p->b+y, p->b+i);
      restore_down(p, y);
    }
  }
}

// Next digit
int next(int* p)
{
  int c;
  while (!isdigit(c = getchar()) && EOF != c)
    ;
  while (isdigit(c))
  {
    *p = *p * 10 + (c - '0');
    c = getchar();
  }
  return c;
}

int main(int argc, const char *argv[])
{
  int a, b, r = 0;
  for (a = b = 0; next(&a) != EOF && next(&b) != EOF; a = b = 0)
  {
    push(a, &g_a);
    push(b, &g_b);
  }
  for (a = min(&g_a), b = min(&g_b); -1 != a; a = min(&g_a), b = min(&g_b))
  {
    r += (a - b) < 0 ? -(a - b) : (a - b);
  }
  printf("%d\n", r);
}