/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|}