03b.c

   1 #include <stdio.h>
   2 #include <stdbool.h>
   3
   4 #define bitread(value, bit) (((value) >> (bit)) & 0x01)
   5
   6 int incremental_search(unsigned numbers[], int len, int bits, bool inv)
   7 {
   8         //Copy for the initial search
   9         int cur[len];
  10         int curlen;
  11         for (curlen = 0; curlen<len; curlen++)
  12                 cur[curlen] = numbers[curlen];
  13
  14         for (int bit = bits-1; bit >= 0 || curlen > 1; bit--) {
  15                 //Determine 0 1 distribution
  16                 int dist = 0;
  17                 for (int i = 0; i<curlen; i++)
  18                         dist += bitread(cur[i], bit) == 0 ? -1 : 1;
  19
  20                 dist = dist >= 0;
  21                 dist = inv ? 1-dist : dist;
  22
  23                 //Filter out numbers
  24                 int newcurlen = 0;
  25                 for (int i = 0; i<curlen; i++)
  26                         if (bitread(cur[i], bit) == dist)
  27                                 cur[newcurlen++] = cur[i];
  28                 curlen = newcurlen;
  29         }
  30         return cur[0];
  31 }
  32
  33 int main(void)
  34 {
  35         unsigned numbers[2000] = {0};
  36         int c = 0, y = 0, maxbits = 0, bits = 0;
  37         while ((c = getchar()) != EOF) {
  38                 if (c == '\n') {
  39                         maxbits = bits > maxbits ? bits : maxbits;
  40                         bits = 0;
  41                         y++;
  42                 } else {
  43                         numbers[y] *= 2;
  44                         if (c == '1')
  45                                 numbers[y]++;
  46                 }
  47         }
  48
  49         int oxygen = incremental_search(numbers, y, maxbits, false);
  50         int co2 = incremental_search(numbers, y, maxbits, true);
  51
  52         printf("%d\n", oxygen*co2);
  53         return 0;
  54 }