/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|   498k|  def set(K k, V v) -> void {
   15|   498k|    u32 hash = k * r >> shift;
   16|   577k|    for (;;) {
   17|   577k|      if (use[hash] == 0) {
  ------------------
  |  Branch (17:11): [True: 48.72%, False: 51.28%]
  ------------------
   18|   281k|        key[hash] = k;
   19|   281k|        use[hash] = 1;
   20|   281k|        val[hash] = v;
   21|   281k|        return;
   22|   281k|      }
   23|   296k|      if (key[hash] == k) {
  ------------------
  |  Branch (23:11): [True: 73.25%, False: 26.75%]
  ------------------
   24|   217k|        val[hash] = v;
   25|   217k|        return;
   26|   217k|      }
   27|  79.2k|      (++hash) &= (N - 1);
   28|  79.2k|    }
   29|   498k|  }
   30|   501k|  def get(K k) -> V {
   31|   501k|    u32 hash = k * r >> shift;
   32|   580k|    for (;;) {
   33|   580k|      if (use[hash] == 0) {
  ------------------
  |  Branch (33:11): [True: 48.69%, False: 51.31%]
  ------------------
   34|   282k|        return 0;
   35|   282k|      }
   36|   298k|      if (key[hash] == k) {
  ------------------
  |  Branch (36:11): [True: 73.34%, False: 26.66%]
  ------------------
   37|   218k|        return val[hash];
   38|   218k|      }
   39|  79.4k|      (++hash) &= (N - 1);
   40|  79.4k|    }
   41|   501k|  }
   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.85%, False: 50.15%]
  ------------------
   58|   498k|      let k = rd.ud();
   59|   498k|      let v = rd.ud();
   60|   498k|      hash_map.set(k, v);
   61|   498k|    }
   62|  1.00M|    if (t == 1) {
  ------------------
  |  Branch (62:9): [True: 50.15%, False: 49.85%]
  ------------------
   63|   501k|      let k = rd.ud();
   64|   501k|      let v = hash_map.get(k);
   65|   501k|      wt.ud(v);
   66|   501k|    }
   67|  1.00M|  }
   68|      1|  return 0;
   69|      1|}