This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub toyama1710/cpp_library
#define PROBLEM "https://judge.yosupo.jp/problem/associative_array" #include <iostream> #include "../../hash_map/array_mapped_trie.hpp" #include "../../util/xorshift.hpp" #define _overload(_1, _2, _3, _4, name, ...) name #define _rep1(Itr, N) _rep3(Itr, 0, N, 1) #define _rep2(Itr, a, b) _rep3(Itr, a, b, 1) #define _rep3(Itr, a, b, step) for (i64 Itr = a; Itr < b; Itr += step) #define repeat(...) _overload(__VA_ARGS__, _rep3, _rep2, _rep1)(__VA_ARGS__) #define rep(...) repeat(__VA_ARGS__) #define ALL(X) begin(X), end(X) using namespace std; using i64 = long long; using u64 = unsigned long long; u64 h(i64 k) { xorshift64 rnd(k); rnd(); rnd(); rnd(); return rnd(); }; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); i64 q; cin >> q; ArrayMappedTrie<i64, 40, 4> mp; rep(_, q) { i64 com, k, v; cin >> com; if (com == 0) { cin >> k >> v; mp[h(k)] = v; } else if (com == 1) { cin >> k; cout << mp[h(k)] << endl; } } return 0; }
#line 1 "test/yosupo/associative_array_amt.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/associative_array" #include <iostream> #line 1 "hash_map/array_mapped_trie.hpp" #include <cstdint> template <class T, int key_width = 32, int chunk_width = 4> struct ArrayMappedTrie { using u64 = uint64_t; static constexpr u64 mask = (1 << chunk_width) - 1; union Node { Node *link[1 << chunk_width]; T dat; Node() : link{} {}; }; Node *root; const T id; ArrayMappedTrie(T id = T()) : root(new Node()), id(id){}; Node *get_node(u64 idx) { Node *u = root; for (int i = 0; i < (key_width + chunk_width - 1) / chunk_width; i++) { if (!u->link[idx & mask]) u->link[idx & mask] = new Node(); u = u->link[idx & mask]; idx >>= chunk_width; } return u; }; bool find(u64 idx) { Node *u = root; u64 i = 0; while (i < (key_width + chunk_width - 1) / chunk_width && !u) { u = u->link[idx & mask]; idx >>= chunk_width; } return u != nullptr; }; T &operator[](u64 idx) { if (find(idx)) { return get_node(idx)->dat; } else { return get_node(idx)->dat = id; } }; }; #line 1 "util/xorshift.hpp" #line 5 "util/xorshift.hpp" struct xorshift32 { uint32_t seed; xorshift32(uint32_t seed = 1710) : seed(seed){}; void set_seed(uint32_t s) { seed = s; }; uint32_t gen() { seed = seed ^ (seed << 13); seed = seed ^ (seed >> 17); seed = seed ^ (seed << 5); return seed; }; uint32_t operator()() { return gen(); }; }; struct xorshift64 { uint64_t seed; xorshift64(uint64_t seed = 1710) : seed(seed){}; void set_seed(uint64_t s) { seed = s; }; uint64_t gen() { seed = seed ^ (seed << 13); seed = seed ^ (seed >> 7); seed = seed ^ (seed << 17); return seed; }; uint64_t operator()() { return gen(); }; }; #line 7 "test/yosupo/associative_array_amt.test.cpp" #define _overload(_1, _2, _3, _4, name, ...) name #define _rep1(Itr, N) _rep3(Itr, 0, N, 1) #define _rep2(Itr, a, b) _rep3(Itr, a, b, 1) #define _rep3(Itr, a, b, step) for (i64 Itr = a; Itr < b; Itr += step) #define repeat(...) _overload(__VA_ARGS__, _rep3, _rep2, _rep1)(__VA_ARGS__) #define rep(...) repeat(__VA_ARGS__) #define ALL(X) begin(X), end(X) using namespace std; using i64 = long long; using u64 = unsigned long long; u64 h(i64 k) { xorshift64 rnd(k); rnd(); rnd(); rnd(); return rnd(); }; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); i64 q; cin >> q; ArrayMappedTrie<i64, 40, 4> mp; rep(_, q) { i64 com, k, v; cin >> com; if (com == 0) { cin >> k >> v; mp[h(k)] = v; } else if (com == 1) { cin >> k; cout << mp[h(k)] << endl; } } return 0; }