kad.c

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

static void printul(unsigned long value) {
  static unsigned char digits[24];
  unsigned char i, n;

  i = 19;
  do {
    n = value % 10;
    digits[--i] = n + '0';
    value /= 10;
  } while (value != 0);
  do {
    putchar_unlocked(digits[i]);
  } while(++i<19);
  putchar_unlocked('\n');
}

#define PREFIX_BITS 9
#define BUCKET_SIZE_LOG2 10

static unsigned long numbers[(1 << PREFIX_BITS) << BUCKET_SIZE_LOG2];

static void insert(unsigned long l, unsigned long *values) {
  (*values)++;
  values[*values] = l;
}

static void add(unsigned long l) {
  insert(l, &numbers[(l >> (64 - PREFIX_BITS - BUCKET_SIZE_LOG2)) & ~0x3FF]);
}

static void findNeighbor(unsigned long l) {
  unsigned long *bucket = &numbers[(l >> (64 - PREFIX_BITS - BUCKET_SIZE_LOG2)) & ~0x3FF];
  int num_in_bucket = bucket[0];
  for (int i = 1; i <= num_in_bucket; i++) {
    unsigned long best = bucket[i];
    unsigned long best_dist = best ^ l;
    for (int j = i+1; j <= num_in_bucket; j++) {
      unsigned long new_best = bucket[j];
      unsigned long new_dist = new_best ^ l;
      if ((new_dist) < (best_dist)) {
        best = new_best;
        best_dist = new_dist;
      }
    }
    printul(best);
    return;
  }
}

static void scanIntoBuckets()
{
  int c = getchar_unlocked();
  do {
    unsigned long l = 0;
    do {
      l = 10 * l + c - 48;
      c = getchar_unlocked();
    } while(c>='0' && c<='9');
    add(l);
    c = getchar_unlocked();
  } while(c>='0' && c<='9');
}

static void scanBucketQueries()
{
  unsigned long c = getchar_unlocked();
  do {
    unsigned long l = 0;
    do {
      l = 10 * l + c - 48;
      c = getchar_unlocked();
    } while(c>='0' && c<='9');
    findNeighbor(l);
    c = getchar_unlocked();
  } while(c>='0' && c<='9');
}

static int scanIntoArray()
{
  int n = 0;
  int c = getchar_unlocked();
  do {
    unsigned long l = 0;
    do {
      l = 10 * l + c - 48;
      c = getchar_unlocked();
    } while(c>='0' && c<='9');
    numbers[n++] = l;
    c = getchar_unlocked();
  } while(c>='0' && c<='9');
  return n;
}

static void findNeighbors(unsigned long l, int find_n, int n)
{
  static unsigned long results[11];
  int num_results = 1;

  results[0] = numbers[0];

  for(int i = 1; i < n; i++) {
    unsigned long dist = numbers[i] ^ l;
    for(int j = num_results-1; j >= 0; j--) {
      if (dist < (results[j] ^ l)) {
        results[j+1] = results[j];
        if (j == 0) {
          results[0] = numbers[i];
          break;
        }
      } else {
        results[j+1] = numbers[i];
        if (num_results < find_n) { num_results++; }
        break;
      }
    }
  }
  for(int i = 0; i < find_n; i++) { printul(results[i]); }
}

static void scanArrayQueries(int find_n, int n)
{
  unsigned long c = getchar_unlocked();
  do {
    unsigned long l = 0;
    do {
      l = 10 * l + c - 48;
      c = getchar_unlocked();
    } while(c>='0' && c<='9');
    findNeighbors(l, find_n, n);
    c = getchar_unlocked();
  } while(c>='0' && c<='9');
}

int main(int, char **argv) {
  int find_n = strtoul(argv[1]+15, NULL, 10);
  if (find_n == 1) {
    scanIntoBuckets();
    scanBucketQueries();
  } else {
    int n = scanIntoArray();
    scanArrayQueries(find_n, n);
  }
  return 0;
}

Makefile

.PHONY: all check-syntax

all:
	g++ $(CFLAGS) -Wall -Wextra -funroll-loops -O3 -pthread -march=native -mtune=native -o run *.c

check-syntax:
	$(CC) $(CFLAGS) -Wall -Wextra -0pedantic -fsyntax-only $(CHK_SOURCES)