Main.java

import java.util.Scanner;

class Main {
  public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    Main hashing = new Main();
    int t = in.nextInt();
    for(int t = in.nextInt(); t > 0; t--) {
      int m = in.nextInt();
      int n = in.nextInt();
      int[] nums = read_in(n, in);
      for(int hash_config: hash_configs) {
        int[] array = new int[m];
        int collisions = hashing.hash(hash_config, nums, array, m);
        StringBuilder sb = new StringBuilder(m*2 + 1);
        sb.append(collisions);
        for(int k_i : array) {
          sb.append(' ');
          sb.append(k_i);
        }
        System.out.println(sb.toString());
      }
    }
  }

  int[] read_in(int n, Scanner in) {
    int[] array = new int[n];
    for(int i = 0; i < n; i++) {
      array[i] = in.nextInt();
    }
    return array;
  }

  static final int LINEAR 	= 1 << 0;
  static final int QUADRATIC 	= 1 << 1;
  static final int DOUBLE 	= 1 << 2;
  static final int[] hash_configs = new int[] { LINEAR, QUADRATIC, DOUBLE };

  int hash(int hash_config, int[] nums, int[] array, int m) {
    int collisions = 0;
    for(int k_i: nums) {
      final int h = mmod(k_i, m);
      int h_s = h;
      int j = 0;
      while(array[h_s] != 0) {
        collisions += 1;
        j += 1;
        h_s = h - s(hash_config, j, k_i, m);
        // assure boundaries (care: not described in sheet)
        h_s = mmod(h_s, m);
      }
      array[h_s] = k_i;
    }
    return collisions;
  }

  int s(int hash_config, int j, int k_i, int m) {
    // choose what to hash based on hash_config
    int l = (hash_config & LINEAR) 	!= 0 ? linear(j) : 0;
    int q = (hash_config & QUADRATIC) 	!= 0 ? quadratic(j) : 0;
    int d = (hash_config & DOUBLE)	!= 0 ? double_hashing(j, k_i, m) : 0;
    return l + q + d;
  }

  int linear(int j) {
    return j;
  }
  int quadratic(int j) {
    int idx = j/2 + mmod(j,2); // ceil(j/2)^2
    idx *= idx;
    return (-idx)*((j % 2) - 1);
  }
  int double_hashing(int j, int k_i, int m) {
    int h_help = 1 + mmod(k_i, m-2);
    return j*h_help;
  }

  // "mathematical" modulo. that is, it's always 0 <= (i % m) < m
  int mmod(int i, int m) {
    int mod = i % m;
    return mod < 0 ? mod + m : mod;
  }
}