Submit Info #65497

Problem Lang User Status Time Memory
Associative Array cpp anonymous AC 128 ms 20.81 MiB

ケース詳細
Name Status Time Memory
2_powers_00 AC 94 ms 17.29 MiB
example_00 AC 8 ms 16.45 MiB
many_0set_00 AC 103 ms 19.08 MiB
many_0set_sparse_00 AC 38 ms 18.34 MiB
max_random_00 AC 118 ms 20.81 MiB
max_random_01 AC 128 ms 20.45 MiB
max_random_02 AC 125 ms 20.04 MiB
random_00 AC 50 ms 17.41 MiB
random_01 AC 56 ms 17.70 MiB
random_02 AC 73 ms 17.55 MiB
sparse_keys_00 AC 47 ms 19.89 MiB
sparse_keys_01 AC 53 ms 20.54 MiB
unordered_map_killer_00 AC 93 ms 17.33 MiB
unordered_map_killer_01 AC 92 ms 17.38 MiB
unordered_map_killer_02 AC 77 ms 17.36 MiB

#include <cstdint> #include <cstdio> #include <bitset> using i32 = std::int32_t; using u32 = std::uint32_t; using i64 = std::int64_t; using u64 = std::uint64_t; template<typename Int> Int in(void) { Int c, x = 0, f = 1; while (c = getchar_unlocked(), c < 48 || c > 57) if (c == 45) f = -f; while (47 < c && c < 58) { x = x * 10 + c - 48; c = getchar_unlocked(); } return f * x; } template<typename Unsigned> Unsigned inu(void) { Unsigned c, x = 0; while (c = getchar_unlocked(), c < 48 || c > 57); while (47 < c && c < 58) { x = x * 10 + c - 48; c = getchar_unlocked(); } return x; } template<typename Int> void out(Int x) { if (x < 0) { putchar_unlocked('-'); x = -x; } if (x >= 10) out(x / 10); putchar_unlocked(x - x / 10 * 10 + 48); } template<typename Unsigned> void outu(Unsigned x) { if (x >= 10) outu(x / 10); putchar_unlocked(x - x / 10 * 10 + 48); } template<typename Key, typename Val> class Hash_Map { private: static constexpr int LG = 20; static constexpr int N = 1 << LG; static constexpr u64 r = 11995408973635179863ull; static constexpr u32 hash(const u64 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 (u32 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]; } } } }; int main() { Hash_Map<u64, u64> hm; i32 Q = in<i32>(); while (Q--) { int t = in<int>(); if (t == 0) { u64 key = inu<u64>(); u64 val = inu<u64>(); hm[key] = val; } else { u64 key = inu<u64>(); outu<u64>(hm[key]); putchar_unlocked('\n'); } } }