Submit Info #64472

Problem Lang User Status Time Memory
Associative Array cpp-acl KoD AC 178 ms 121.42 MiB

ケース詳細
Name Status Time Memory
2_powers_00 AC 178 ms 121.42 MiB
example_00 AC 1 ms 0.57 MiB
many_0set_00 AC 102 ms 30.95 MiB
many_0set_sparse_00 AC 16 ms 2.57 MiB
max_random_00 AC 103 ms 31.08 MiB
max_random_01 AC 110 ms 30.93 MiB
max_random_02 AC 106 ms 30.94 MiB
random_00 AC 50 ms 31.06 MiB
random_01 AC 56 ms 31.00 MiB
random_02 AC 69 ms 30.94 MiB
sparse_keys_00 AC 17 ms 4.20 MiB
sparse_keys_01 AC 20 ms 4.77 MiB
unordered_map_killer_00 AC 168 ms 121.38 MiB
unordered_map_killer_01 AC 168 ms 121.36 MiB
unordered_map_killer_02 AC 158 ms 121.36 MiB

#define PROBLEM "https://judge.yosupo.jp/problem/associative_array" #include <cstddef> #include <cstdint> using i32 = std::int32_t; using u32 = std::uint32_t; using i64 = std::int64_t; using u64 = std::uint64_t; using isize = std::ptrdiff_t; using usize = std::size_t; #include <bits/stdc++.h> __attribute__((target("avx2"))) constexpr u64 ceil_log2(const u64 x) { u64 e = 0; while (((u64)1 << e) < x) ++e; return e; } u64 xorshift() { static u64 state = std::chrono::system_clock::now().time_since_epoch().count(); state ^= state << 7; state ^= state >> 9; return state; } class rep { struct Iter { usize itr; constexpr Iter(const usize pos) noexcept : itr(pos) {} constexpr void operator++() noexcept { ++itr; } constexpr bool operator!=(const Iter &other) const noexcept { return itr != other.itr; } constexpr usize operator*() const noexcept { return itr; } }; const Iter first, last; public: explicit constexpr rep(const usize first, const usize last) noexcept : first(first), last(std::max(first, last)) {} constexpr Iter begin() const noexcept { return first; } constexpr Iter end() const noexcept { return last; } }; template <class K, class V, std::enable_if_t<std::is_integral_v<K>> * = nullptr> class IntegerHashTable { using Self = IntegerHashTable; enum class Ctrl : char { Empty, Full, Deleted }; union Slot { std::pair<const K, V> pair; std::pair<K, V> mut_pair; Slot() {} }; struct Data { Ctrl ctrl; Slot slot; Data() : ctrl(Ctrl::Empty), slot() {} ~Data() { if (ctrl == Ctrl::Full) slot.mut_pair.~pair(); } }; struct Manager { static inline constexpr u64 PHI = 11400714819323198485ull; static inline const u64 RND = xorshift(); usize logn, size, full, deleted; Manager() : logn(0), size(0), full(0), deleted(0) {} void fix() { logn = ceil_log2(4 * full); size = (full == 0 ? 0 : (1 << logn)); deleted = 0; } bool balanced() const { return 2 * (full + deleted) <= size and 8 * full >= size; } usize mask() const { return size - 1; } usize index(const K &k) const { u64 x = static_cast<u64>(k) ^ RND; x ^= x >> (64 - logn); return (x * PHI) >> (64 - logn); } }; Data *data; Manager info; usize find_key(const K &k, usize i) const { while (data[i].ctrl != Ctrl::Empty) { if (data[i].ctrl == Ctrl::Full and data[i].slot.pair.first == k) break; i = (i + 1) & info.mask(); } return i; } usize find_place(usize i) const { while (data[i].ctrl == Ctrl::Full) i = (i + 1) & info.mask(); return i; } template <class... Args> void construct(const usize i, Args &&...args) { new (&data[i].slot.mut_pair) std::pair<K, V>(std::forward<Args>(args)...); } void resize() { Data *old_data = std::exchange(data, nullptr); const usize old_len = info.size; info.fix(); if (info.size) { data = new Data[info.size]; for (const usize i : rep(0, old_len)) { if (old_data[i].ctrl == Ctrl::Full) { const usize k = find_place(info.index(old_data[i].slot.pair.first)); data[k].ctrl = Ctrl::Full; construct(k, std::move(old_data[i].slot.mut_pair)); } } } if (old_data) delete[] old_data; } public: IntegerHashTable() noexcept : data(nullptr), info() {} IntegerHashTable(const Self &other) noexcept : Self() { *this = other; } IntegerHashTable(Self &&other) noexcept : Self() { *this = std::move(other); } ~IntegerHashTable() { clear(); } class Iter { friend class IntegerHashTable; usize idx; Self *self; explicit Iter(const usize i, Self *s) : idx(i - 1), self(s) { next(); } void next() { while (++idx < self->info.size) if (self->data[idx].ctrl == Ctrl::Full) return; } public: bool operator!=(const Iter &other) const { return idx != other.idx or self != other.self; } std::pair<const K, V> &operator*() const { return self->data[idx].slot.pair; } void operator++() { next(); } }; class ConstIter { friend class IntegerHashTable; usize idx; const Self *self; explicit ConstIter(const usize i, const Self *s) : idx(i - 1), self(s) { next(); } void next() { while (++idx < self->info.size) if (self->data[idx].ctrl == Ctrl::Full) return; } public: bool operator!=(const ConstIter &other) const { return idx != other.idx or self != other.self; } const std::pair<const K, V> &operator*() const { return self->data[idx].slot.pair; } void operator++() { next(); } }; Self &operator=(const Self &other) noexcept { if (this != &other) { clear(); info = other.info; info.fix(); if (info.size) { data = new Data[info.size]; for (const usize i : rep(0, other.info.size)) { if (other.data[i].ctrl == Ctrl::Full) { const usize k = find_place(info.index(other.data[i].slot.pair.first)); data[k].ctrl = Ctrl::Full; construct(k, other.data[i].slot.mut_pair); } } } copy(other.data, other.info.size); } return *this; } Self &operator=(Self &&other) noexcept { if (this != &other) { clear(); data = std::exchange(other.data, nullptr); info = std::exchange(other.info, Manager()); } return *this; } template <class... Args> std::pair<V *, bool> insert(const K &key, Args &&...args) { usize idx = -1; if (empty()) { info.full += 1; resize(); idx = info.index(key); } else { const usize pos = info.index(key); usize i = find_key(key, pos); if (data[i].ctrl == Ctrl::Full) return std::make_pair(&data[i].slot.pair.second, false); i = find_place(pos); info.full += 1; info.deleted -= (data[i].ctrl == Ctrl::Deleted); if (!info.balanced()) { resize(); i = find_place(info.index(key)); } idx = i; } data[idx].ctrl = Ctrl::Full; construct(idx, std::piecewise_construct, std::forward_as_tuple(key), std::forward_as_tuple(std::forward<Args>(args)...)); return std::make_pair(&data[idx].slot.pair.second, true); } bool erase(const K &key) { if (empty()) return false; const usize i = find_key(key, info.index(key)); if (data[i].ctrl == Ctrl::Full) { info.full -= 1; info.deleted += 1; data[i].ctrl = Ctrl::Deleted; data[i].slot.mut_pair.~pair(); if (!info.balanced()) resize(); } } void clear() { if (data) { delete[] data; data = nullptr; } info = Manager(); } usize size() const { return info.full; } bool empty() { return size() == 0; } V &operator[](const K &key) { return *insert(key).first; } Iter begin() { return Iter(0, this); } Iter end() { return Iter(info.size, this); } ConstIter begin() const { return ConstIter(0, this); } ConstIter end() const { return ConstIter(info.size, this); } }; class revrep { struct Iter { usize itr; constexpr Iter(const usize pos) noexcept : itr(pos) {} constexpr void operator++() noexcept { --itr; } constexpr bool operator!=(const Iter &other) const noexcept { return itr != other.itr; } constexpr usize operator*() const noexcept { return itr; } }; const Iter first, last; public: explicit constexpr revrep(const usize first, const usize last) noexcept : first(last - 1), last(std::min(first, last) - 1) {} constexpr Iter begin() const noexcept { return first; } constexpr Iter end() const noexcept { return last; } }; namespace fast_io { template <u64 N> constexpr u64 TEN = 10 * TEN<N - 1>; template <> constexpr u64 TEN<0> = 1; constexpr usize BUF_SIZE = 1 << 17; __attribute__((target("avx2"))) inline constexpr usize integer_digits(const u64 n) { if (n >= TEN<10>) { if (n >= TEN<15>) { if (n >= TEN<19>) return 20; if (n >= TEN<18>) return 19; if (n >= TEN<17>) return 18; if (n >= TEN<16>) return 17; return 16; } else { if (n >= TEN<14>) return 15; if (n >= TEN<13>) return 14; if (n >= TEN<12>) return 13; if (n >= TEN<11>) return 12; return 11; } } else { if (n >= TEN<5>) { if (n >= TEN<9>) return 10; if (n >= TEN<8>) return 9; if (n >= TEN<7>) return 8; if (n >= TEN<6>) return 7; return 6; } else { if (n >= TEN<4>) return 5; if (n >= TEN<3>) return 4; if (n >= TEN<2>) return 3; if (n >= TEN<1>) return 2; return 1; } } } struct NumBlock { char NUM[40000]; constexpr NumBlock() : NUM() { for (const auto i : rep(0, 10000)) { auto n = i; for (const auto j : revrep(0, 4)) { NUM[i * 4 + j] = n % 10 + '0'; n /= 10; } } } } constexpr num_block; class Scanner { char buf[BUF_SIZE]; usize left, right; __attribute__((target("avx2"))) inline void load() { const usize len = right - left; std::memcpy(buf, buf + left, len); right = len + std::fread(buf + len, 1, BUF_SIZE - len, stdin); left = 0; } __attribute__((target("avx2"))) inline void ignore_spaces() { while (buf[left] <= ' ') { if (__builtin_expect(++left == right, 0)) load(); } } public: Scanner() : buf(), left(0), right(0) { load(); } __attribute__((target("avx2"))) void scan(char &c) { ignore_spaces(); c = buf[left++]; } template <typename T, std::enable_if_t<std::is_integral_v<T>> * = nullptr> __attribute__((target("avx2"))) inline void scan(T &x) { ignore_spaces(); if (__builtin_expect(left + 32 > right, 0)) load(); char c = buf[left++]; bool minus = false; if constexpr (std::is_signed_v<T>) { if (c == '-') { minus = 1; c = buf[left++]; } } x = 0; while (c >= '0') { x = x * 10 + (c & 15); c = buf[left++]; } if constexpr (std::is_signed_v<T>) { if (minus) x = -x; } } template <class T, class... Args> __attribute__((target("avx2"))) inline void scan(T &x, Args &...args) { scan(x); scan(args...); } }; class Printer { char buf[BUF_SIZE]; usize pos; __attribute__((target("avx2"))) inline void flush() { std::fwrite(buf, 1, pos, stdout); pos = 0; } public: Printer() : buf(), pos(0) {} ~Printer() { flush(); } __attribute__((target("avx2"))) void print(const char c) { buf[pos] = c; if (__builtin_expect(++pos == BUF_SIZE, 0)) flush(); } template <typename T, std::enable_if_t<std::is_integral_v<T>> * = nullptr> __attribute__((target("avx2"))) inline void print(T x) { if (__builtin_expect(pos + 32 > BUF_SIZE, 0)) flush(); if (x == 0) { buf[pos++] = '0'; return; } if constexpr (std::is_signed_v<T>) { if (x < 0) { buf[pos++] = '-'; x = -x; } } const auto digit = integer_digits(x); usize len = digit; while (len >= 4) { len -= 4; std::memcpy(buf + pos + len, num_block.NUM + (x % 10000) * 4, 4); x /= 10000; } std::memcpy(buf + pos, num_block.NUM + x * 4 + 4 - len, len); pos += digit; } template <class T, class... Args> __attribute__((target("avx2"))) inline void print(T x, Args &&...args) { print(x); print(' '); print(std::forward<Args>(args)...); } template <class... Args> __attribute__((target("avx2"))) void println(Args &&...args) { print(std::forward<Args>(args)...); print('\n'); } }; }; // namespace fast_io int main() { fast_io::Scanner scan; fast_io::Printer print; usize Q; // std::cin >> Q; scan.scan(Q); IntegerHashTable<u64, u64> map; while (Q--) { char c; u64 k; scan.scan(c, k); // std::cin >> c >> k; if (c == '0') { u64 v; // std::cin >> v; scan.scan(v); map[k] = v; } else { // std::cout << map[k] << '\n'; print.println(map[k]); } } return 0; }