/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|   759k|    for (;;) {
   17|   759k|      if (use[hash] == 0) {
  ------------------
  |  Branch (17:11): [True: 65.77%, False: 34.23%]
  ------------------
   18|   499k|        key[hash] = k;
   19|   499k|        use[hash] = 1;
   20|   499k|        val[hash] = v;
   21|   499k|        return;
   22|   499k|      }
   23|   260k|      if (key[hash] == k) {
  ------------------
  |  Branch (23:11): [True: 0.00%, False: 100.00%]
  ------------------
   24|      0|        val[hash] = v;
   25|      0|        return;
   26|      0|      }
   27|   260k|      (++hash) &= (N - 1);
   28|   260k|    }
   29|   499k|  }
   30|   500k|  def get(K k) -> V {
   31|   500k|    u32 hash = k * r >> shift;
   32|   761k|    for (;;) {
   33|   761k|      if (use[hash] == 0) {
  ------------------
  |  Branch (33:11): [True: 65.70%, False: 34.30%]
  ------------------
   34|   500k|        return 0;
   35|   500k|      }
   36|   261k|      if (key[hash] == k) {
  ------------------
  |  Branch (36:11): [True: 0.00%, False: 100.00%]
  ------------------
   37|      0|        return val[hash];
   38|      0|      }
   39|   261k|      (++hash) &= (N - 1);
   40|   261k|    }
   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|}