Submit Info #65494

Problem Lang User Status Time Memory
Associative Array cpp anonymous AC 360 ms 20.98 MiB

ケース詳細
Name Status Time Memory
2_powers_00 AC 339 ms 17.45 MiB
example_00 AC 8 ms 16.57 MiB
many_0set_00 AC 324 ms 19.16 MiB
many_0set_sparse_00 AC 110 ms 18.44 MiB
max_random_00 AC 342 ms 20.98 MiB
max_random_01 AC 336 ms 20.63 MiB
max_random_02 AC 348 ms 20.12 MiB
random_00 AC 137 ms 17.45 MiB
random_01 AC 161 ms 17.85 MiB
random_02 AC 214 ms 17.72 MiB
sparse_keys_00 AC 118 ms 19.99 MiB
sparse_keys_01 AC 137 ms 20.70 MiB
unordered_map_killer_00 AC 360 ms 17.46 MiB
unordered_map_killer_01 AC 357 ms 17.43 MiB
unordered_map_killer_02 AC 328 ms 17.44 MiB

#include <cstdint> #include <cstdio> #include <bitset> #include <vector> template<typename Key, typename Val> class Hash_Map { private: static constexpr int LG = 20; static constexpr int N = 1 << LG; static constexpr std::uint64_t r = 11995408973635179863ull; static constexpr std::uint32_t hash(const std::uint64_t a) { return (a * r) >> (64 - LG); } std::bitset<N> m_used; Key m_keys[N]; Val m_vals[N]; public: Hash_Map() = default; Val& operator[](const Key &key) { for (std::uint32_t i = hash(key);; (i += 1) &= (N - 1)) { if (not m_used.test(i)) { m_keys[i] = key; m_used.set(i); return m_vals[i] = Val{}; } if (m_keys[i] == key) { return m_vals[i]; } } } }; struct XorShift { private: constexpr static double R = 1.0 / 0xffffffff; std::uint64_t x; public: explicit XorShift(std::uint64_t seed = 88172645463325252ull): x(seed) {} template<typename T = std::uint64_t> inline T get() { x ^= x << 7ull; x ^= x >> 9ull; return x; } inline std::uint32_t get(std::uint32_t r) { return std::uint64_t(get<std::uint32_t>() * r) >> 32ul; } inline std::uint32_t get(std::uint32_t l, std::uint32_t r) { return l + get(r - l); } inline double probability() { return get<std::uint32_t>() * R; } }; struct SplitMix64 { private: constexpr static std::uint64_t increment = 11400714819323198485ull; constexpr static double R = 1.0 / 0xffffffff; std::uint64_t x; public: explicit SplitMix64(std::uint64_t seed = 1991220599727906348ull): x(seed) {} template<typename T = std::uint64_t> inline T get() { x += increment; std::uint64_t z = x; z = (z ^ (z >> 30)) * 13787848793156543929ull; z = (z ^ (z >> 27)) * 10723151780598845931ull; z = z ^ (z >> 31); return z; } inline std::uint32_t get(std::uint32_t r) { return std::uint64_t(get<std::uint32_t>() * r) >> 32ul; } inline std::uint32_t get(std::uint32_t l, std::uint32_t r) { return l + get(r - l); } inline double probability() { return get<std::uint32_t>() * R; } }; void radix_sort32(std::vector<std::uint32_t> &a) { std::vector<std::uint32_t> work0(256); std::vector<std::uint32_t> work1(a.size()); std::vector<std::uint32_t> work2(256); std::uint32_t s = 0; std::uint64_t x = 0; while (s < 32u) { std::fill_n(work2.begin(), 256, 0); for (int i = 0; i < int(a.size()); i++) { x = (a[i] >> s) & 0xff; work2[x]++; work1[i] = a[i]; } work0[0] = 0; for (int i = 0; i < 255; i++) work0[i + 1] = work0[i] + work2[i]; for (int i = 0; i < int(a.size()); i++) { x = (work1[i] >> s) & 255; a[work0[x]] = work1[i]; work0[x]++; } s += 8u; } } void radix_sort64(std::vector<std::uint64_t> &a) { std::vector<std::uint64_t> work0(65536); std::vector<std::uint64_t> work1(a.size()); std::vector<std::uint64_t> work2(65536); std::uint32_t s = 0; std::uint64_t x = 0; while (s < 64ul) { std::fill_n(work2.begin(), 65536, 0); for (int i = 0; i < int(a.size()); i++) { x = (a[i] >> s) & 65535; work2[x]++; work1[i] = a[i]; } work0[0] = 0; for (int i = 0; i < 65535; i++) work0[i + 1] = work0[i] + work2[i]; for (int i = 0; i < int(a.size()); i++) { x = (work1[i] >> s) & 65535; a[work0[x]] = work1[i]; work0[x]++; } s += 16; } } template<typename T> void comb_sort11(std::vector<T> &a) { int f, g; f = g = int(a.size()); while (true) { bool no_swap = true; g = std::max((g * 10) / 13, 1); if (g == 9 || g == 10) g = 11; for (int i = 0; i + g < f; i++) { if (a[i] > a[i + g]) { std::swap(a[i], a[i + g]); no_swap = false; } } if (g == 1 && no_swap) break; } } int main() { Hash_Map<std::uint64_t, std::uint64_t> dict; int Q; scanf("%d", &Q); while (Q--) { int t; scanf("%d", &t); if (t == 0) { std::uint64_t k, v; scanf("%lu%lu", &k, &v); dict[k] = v; } else { std::uint64_t k; scanf("%lu", &k); printf("%lu\n", dict[k]); } } }