/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|  7.12M|  def set(K k, V v) -> void {
   15|  7.12M|    u32 hash = k * r >> shift;
   16|  16.5M|    for (;;) {
   17|  16.5M|      if (use[hash] == 0) {
  ------------------
  |  Branch (17:11): [True: 31.21%, False: 68.79%]
  ------------------
   18|  5.17M|        key[hash] = k;
   19|  5.17M|        use[hash] = 1;
   20|  5.17M|        val[hash] = v;
   21|  5.17M|        return;
   22|  5.17M|      }
   23|  11.4M|      if (key[hash] == k) {
  ------------------
  |  Branch (23:11): [True: 17.11%, False: 82.89%]
  ------------------
   24|  1.95M|        val[hash] = v;
   25|  1.95M|        return;
   26|  1.95M|      }
   27|  9.45M|      (++hash) &= (N - 1);
   28|  9.45M|    }
   29|  7.12M|  }
   30|  6.54M|  def get(K k) -> V {
   31|  6.54M|    u32 hash = k * r >> shift;
   32|  7.84M|    for (;;) {
   33|  7.84M|      if (use[hash] == 0) {
  ------------------
  |  Branch (33:11): [True: 63.56%, False: 36.44%]
  ------------------
   34|  4.98M|        return 0;
   35|  4.98M|      }
   36|  2.85M|      if (key[hash] == k) {
  ------------------
  |  Branch (36:11): [True: 54.75%, False: 45.25%]
  ------------------
   37|  1.56M|        return val[hash];
   38|  1.56M|      }
   39|  1.29M|      (++hash) &= (N - 1);
   40|  1.29M|    }
   41|  6.54M|  }
   42|       |};
   43|       |
   44|       |HashMap<u64, u64, 1 << 20> hash_map;
   45|       |
   46|       |} // namespace
   47|       |
   48|     18|int main() {
   49|     18|  rd rd;
   50|     18|  wt wt;
   51|     18|  int q = rd.uh();
   52|     18|#ifdef LOCAL
   53|     18|  hash_map.use.reset();
   54|     18|#endif
   55|  13.6M|  while (q--) {
  ------------------
  |  Branch (55:10): [True: 100.00%, False: 0.00%]
  ------------------
   56|  13.6M|    let t = rd.u1();
   57|  13.6M|    if (t == 0) {
  ------------------
  |  Branch (57:9): [True: 52.11%, False: 47.89%]
  ------------------
   58|  7.12M|      let k = rd.ud();
   59|  7.12M|      let v = rd.ud();
   60|  7.12M|      hash_map.set(k, v);
   61|  7.12M|    }
   62|  13.6M|    if (t == 1) {
  ------------------
  |  Branch (62:9): [True: 47.89%, False: 52.11%]
  ------------------
   63|  6.54M|      let k = rd.ud();
   64|  6.54M|      let v = hash_map.get(k);
   65|  6.54M|      wt.ud(v);
   66|  6.54M|    }
   67|  13.6M|  }
   68|     18|  return 0;
   69|     18|}