/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|   499k|  def set(K k, V v) -> void {
   15|   499k|    u32 hash = k * r >> shift;
   16|   603k|    for (;;) {
   17|   603k|      if (use[hash] == 0) {
  ------------------
  |  Branch (17:11): [True: 55.41%, False: 44.59%]
  ------------------
   18|   334k|        key[hash] = k;
   19|   334k|        use[hash] = 1;
   20|   334k|        val[hash] = v;
   21|   334k|        return;
   22|   334k|      }
   23|   269k|      if (key[hash] == k) {
  ------------------
  |  Branch (23:11): [True: 61.36%, False: 38.64%]
  ------------------
   24|   165k|        val[hash] = v;
   25|   165k|        return;
   26|   165k|      }
   27|   104k|      (++hash) &= (N - 1);
   28|   104k|    }
   29|   499k|  }
   30|   500k|  def get(K k) -> V {
   31|   500k|    u32 hash = k * r >> shift;
   32|   604k|    for (;;) {
   33|   604k|      if (use[hash] == 0) {
  ------------------
  |  Branch (33:11): [True: 55.48%, False: 44.52%]
  ------------------
   34|   335k|        return 0;
   35|   335k|      }
   36|   268k|      if (key[hash] == k) {
  ------------------
  |  Branch (36:11): [True: 61.38%, False: 38.62%]
  ------------------
   37|   165k|        return val[hash];
   38|   165k|      }
   39|   103k|      (++hash) &= (N - 1);
   40|   103k|    }
   41|   500k|  }
   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|  1.00M|  while (q--) {
  ------------------
  |  Branch (55:10): [True: 100.00%, False: 0.00%]
  ------------------
   56|  1.00M|    let t = rd.u1();
   57|  1.00M|    if (t == 0) {
  ------------------
  |  Branch (57:9): [True: 49.97%, False: 50.03%]
  ------------------
   58|   499k|      let k = rd.ud();
   59|   499k|      let v = rd.ud();
   60|   499k|      hash_map.set(k, v);
   61|   499k|    }
   62|  1.00M|    if (t == 1) {
  ------------------
  |  Branch (62:9): [True: 50.03%, False: 49.97%]
  ------------------
   63|   500k|      let k = rd.ud();
   64|   500k|      let v = hash_map.get(k);
   65|   500k|      wt.ud(v);
   66|   500k|    }
   67|  1.00M|  }
   68|      1|  return 0;
   69|      1|}