/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|   194k|  def set(K k, V v) -> void {
   15|   194k|    u32 hash = k * r >> shift;
   16|   194k|    for (;;) {
   17|   194k|      if (use[hash] == 0) {
  ------------------
  |  Branch (17:11): [True: 0.02%, False: 99.98%]
  ------------------
   18|     43|        key[hash] = k;
   19|     43|        use[hash] = 1;
   20|     43|        val[hash] = v;
   21|     43|        return;
   22|     43|      }
   23|   194k|      if (key[hash] == k) {
  ------------------
  |  Branch (23:11): [True: 100.00%, False: 0.00%]
  ------------------
   24|   194k|        val[hash] = v;
   25|   194k|        return;
   26|   194k|      }
   27|      0|      (++hash) &= (N - 1);
   28|      0|    }
   29|   194k|  }
   30|   194k|  def get(K k) -> V {
   31|   194k|    u32 hash = k * r >> shift;
   32|   194k|    for (;;) {
   33|   194k|      if (use[hash] == 0) {
  ------------------
  |  Branch (33:11): [True: 0.02%, False: 99.98%]
  ------------------
   34|     36|        return 0;
   35|     36|      }
   36|   194k|      if (key[hash] == k) {
  ------------------
  |  Branch (36:11): [True: 100.00%, False: 0.00%]
  ------------------
   37|   194k|        return val[hash];
   38|   194k|      }
   39|      0|      (++hash) &= (N - 1);
   40|      0|    }
   41|   194k|  }
   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|   389k|  while (q--) {
  ------------------
  |  Branch (55:10): [True: 100.00%, False: 0.00%]
  ------------------
   56|   389k|    let t = rd.u1();
   57|   389k|    if (t == 0) {
  ------------------
  |  Branch (57:9): [True: 50.00%, False: 50.00%]
  ------------------
   58|   194k|      let k = rd.ud();
   59|   194k|      let v = rd.ud();
   60|   194k|      hash_map.set(k, v);
   61|   194k|    }
   62|   389k|    if (t == 1) {
  ------------------
  |  Branch (62:9): [True: 50.00%, False: 50.00%]
  ------------------
   63|   194k|      let k = rd.ud();
   64|   194k|      let v = hash_map.get(k);
   65|   194k|      wt.ud(v);
   66|   194k|    }
   67|   389k|  }
   68|      1|  return 0;
   69|      1|}