/tmp/solutions/build/associative_array-main.cpp:
    1|       |#include <common.h>
    2|       |#include <toy/bit.h>
    3|       |prelude;
    4|       |
    5|       |namespace {
    6|       |
    7|       |template <typename K, typename V, u32 N> struct HashMap {
    8|       |  static_assert(has_single_bit(N));
    9|       |  K key[N];
   10|       |  V val[N];
   11|       |  std::bitset<N> use;
   12|       |  static constexpr u32 shift = 64 - log(N);
   13|       |  static constexpr u64 r = 11995408973635179863ULL;
   14|      3|  def set(K k, V v) -> void {
   15|      3|    u32 hash = k * r >> shift;
   16|      3|    for (;;) {
   17|      3|      if (use[hash] == 0) {
  ------------------
  |  Branch (17:11): [True: 66.67%, False: 33.33%]
  ------------------
   18|      2|        key[hash] = k;
   19|      2|        use[hash] = 1;
   20|      2|        val[hash] = v;
   21|      2|        return;
   22|      2|      }
   23|      1|      if (key[hash] == k) {
  ------------------
  |  Branch (23:11): [True: 100.00%, False: 0.00%]
  ------------------
   24|      1|        val[hash] = v;
   25|      1|        return;
   26|      1|      }
   27|      0|      (++hash) &= (N - 1);
   28|      0|    }
   29|      3|  }
   30|      5|  def get(K k) -> V {
   31|      5|    u32 hash = k * r >> shift;
   32|      5|    for (;;) {
   33|      5|      if (use[hash] == 0) {
  ------------------
  |  Branch (33:11): [True: 20.00%, False: 80.00%]
  ------------------
   34|      1|        return 0;
   35|      1|      }
   36|      4|      if (key[hash] == k) {
  ------------------
  |  Branch (36:11): [True: 100.00%, False: 0.00%]
  ------------------
   37|      4|        return val[hash];
   38|      4|      }
   39|      0|      (++hash) &= (N - 1);
   40|      0|    }
   41|      5|  }
   42|       |};
   43|       |
   44|       |HashMap<u64, u64, 1 << 20> hash_map;
   45|       |
   46|       |} // namespace
   47|       |
   48|      1|int main() {
   49|      1|  rd rd;
   50|      1|  wt wt;
   51|      1|  int q = rd.uh();
   52|      1|#ifdef LOCAL
   53|      1|  hash_map.use.reset();
   54|      1|#endif
   55|      9|  while (q--) {
  ------------------
  |  Branch (55:10): [True: 88.89%, False: 11.11%]
  ------------------
   56|      8|    let t = rd.u1();
   57|      8|    if (t == 0) {
  ------------------
  |  Branch (57:9): [True: 37.50%, False: 62.50%]
  ------------------
   58|      3|      let k = rd.ud();
   59|      3|      let v = rd.ud();
   60|      3|      hash_map.set(k, v);
   61|      3|    }
   62|      8|    if (t == 1) {
  ------------------
  |  Branch (62:9): [True: 62.50%, False: 37.50%]
  ------------------
   63|      5|      let k = rd.ud();
   64|      5|      let v = hash_map.get(k);
   65|      5|      wt.ud(v);
   66|      5|    }
   67|      8|  }
   68|      1|  return 0;
   69|      1|}