Submit Info #65690

Problem Lang User Status Time Memory
Associative Array cpp anonymous AC 104 ms 20.82 MiB

ケース詳細
Name Status Time Memory
2_powers_00 AC 85 ms 17.30 MiB
example_00 AC 8 ms 16.45 MiB
many_0set_00 AC 91 ms 19.14 MiB
many_0set_sparse_00 AC 33 ms 18.32 MiB
max_random_00 AC 104 ms 20.82 MiB
max_random_01 AC 98 ms 20.45 MiB
max_random_02 AC 95 ms 20.05 MiB
random_00 AC 39 ms 17.45 MiB
random_01 AC 47 ms 17.69 MiB
random_02 AC 58 ms 17.58 MiB
sparse_keys_00 AC 40 ms 19.95 MiB
sparse_keys_01 AC 46 ms 20.57 MiB
unordered_map_killer_00 AC 89 ms 17.29 MiB
unordered_map_killer_01 AC 85 ms 17.32 MiB
unordered_map_killer_02 AC 71 ms 17.31 MiB

#pragma region opt #pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma endregion opt #pragma region header #define _GNU_SOURCE #include <stdbool.h> #include <stdint.h> #include <stdio.h> #include <stdlib.h> #include <assert.h> #include <limits.h> #include <math.h> #include <string.h> #include <time.h> #pragma endregion header #pragma region type /* signed integer */ typedef int8_t i8; typedef int16_t i16; typedef int32_t i32; typedef int64_t i64; typedef __int128_t i128; /* unsigned integer */ typedef uint8_t u8; typedef uint16_t u16; typedef uint32_t u32; typedef uint64_t u64; typedef __uint128_t u128; /* floating point number */ typedef float f32; typedef double f64; typedef long double f80; #pragma endregion type #pragma region macro #define MIN(a, b) (((a) < (b)) ? (a) : (b)) #define MAX(a, b) (((a) > (b)) ? (a) : (b)) #define SWAP(a, b) (((a) ^= (b)), ((b) ^= (a)), ((a) ^= (b))) #define POPCNT32(a) __builtin_popcount((a)) #define POPCNT64(a) __builtin_popcountll((a)) #define CTZ32(a) __builtin_ctz((a)) #define CLZ32(a) __builtin_clz((a)) #define CTZ64(a) __builtin_ctzll((a)) #define CLZ64(a) __builtin_clzll((a)) #define HAS_SINGLE_BIT32(a) (__builtin_popcount((a)) == (1)) #define HAS_SINGLE_BIT64(a) (__builtin_popcountll((a)) == (1)) #define MSB32(a) ((31) - __builtin_clz((a))) #define MSB64(a) ((63) - __builtin_clzll((a))) #define BIT_WIDTH32(a) ((a) ? ((32) - __builtin_clz((a))) : (0)) #define BIT_WIDTH64(a) ((a) ? ((64) - __builtin_clzll((a))) : (0)) #define LSBit(a) ((a) & (-(a))) #define CLSBit(a) ((a) & ((a) - (1))) #define BIT_CEIL32(a) ((!(a)) ? (1) : ((POPCNT32(a)) == (1) ? ((1u) << ((31) - CLZ32((a)))) : ((1u) << ((32) - CLZ32(a))))) #define BIT_CEIL64(a) ((!(a)) ? (1) : ((POPCNT64(a)) == (1) ? ((1ull) << ((63) - CLZ64((a)))) : ((1ull) << ((64) - CLZ64(a))))) #define BIT_FLOOR32(a) ((!(a)) ? (0) : ((1u) << ((31) - CLZ32((a))))) #define BIT_FLOOR64(a) ((!(a)) ? (0) : ((1ull) << ((63) - CLZ64((a))))) #define _ROTL32(x, s) (((x) << ((s) % (32))) | (((x) >> ((32) - ((s) % (32)))))) #define _ROTR32(x, s) (((x) >> ((s) % (32))) | (((x) << ((32) - ((s) % (32)))))) #define ROTL32(x, s) (((s) == (0)) ? (x) : ((((i64)(s)) < (0)) ? (_ROTR32((x), -(s))) : (_ROTL32((x), (s))))) #define ROTR32(x, s) (((s) == (0)) ? (x) : ((((i64)(s)) < (0)) ? (_ROTL32((x), -(s))) : (_ROTR32((x), (s))))) #define _ROTL64(x, s) (((x) << ((s) % (64))) | (((x) >> ((64) - ((s) % (64)))))) #define _ROTR64(x, s) (((x) >> ((s) % (64))) | (((x) << ((64) - ((s) % (64)))))) #define ROTL64(x, s) (((s) == (0)) ? (x) : ((((i128)(s)) < (0)) ? (_ROTR64((x), -(s))) : (_ROTL64((x), (s))))) #define ROTR64(x, s) (((s) == (0)) ? (x) : ((((i128)(s)) < (0)) ? (_ROTL64((x), -(s))) : (_ROTR64((x), (s))))) #pragma endregion macro #pragma region io int read_int(void) { // -2147483648 ~ 2147483647 (> 10 ^ 9) 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; } i32 in_i32(void) { // -2147483648 ~ 2147483647 (> 10 ^ 9) i32 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; } u32 in_u32(void) { // 0 ~ 4294967295 (> 10 ^ 9) u32 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; } i64 in_i64(void) { // -9223372036854775808 ~ 9223372036854775807 (> 10 ^ 18) i64 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; } u64 in_u64(void) { // 0 ~ 18446744073709551615 (> 10 ^ 19) u64 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; } static inline void write_int_inner(int x) { if (x >= 10) write_int_inner(x / 10); putchar_unlocked(x - x / 10 * 10 + 48); } void write_int(int x) { if (x < 0) { putchar_unlocked('-'); x = -x; } write_int_inner(x); } static inline void out_i32_inner(i32 x) { if (x >= 10) out_i32_inner(x / 10); putchar_unlocked(x - x / 10 * 10 + 48); } void out_i32(i32 x) { if (x < 0) { putchar_unlocked('-'); x = -x; } out_i32_inner(x); } void out_u32(u32 x) { if (x >= 10) out_u32(x / 10); putchar_unlocked(x - x / 10 * 10 + 48); } static inline void out_i64_inner(i64 x) { if (x >= 10) out_i64_inner(x / 10); putchar_unlocked(x - x / 10 * 10 + 48); } void out_i64(i64 x) { if (x < 0) { putchar_unlocked('-'); x = -x; } out_i64_inner(x); } void out_u64(u64 x) { if (x >= 10) out_u64(x / 10); putchar_unlocked(x - x / 10 * 10 + 48); } void NL(void) { putchar_unlocked('\n'); } void SP(void) { putchar_unlocked(' '); } void write_int_array(int *a, int a_len) { for (int i = 0; i < a_len; i++) { if (i) SP(); write_int(a[i]); } NL(); } void out_i32_array(i32 *a, int a_len) { for (int i = 0; i < a_len; i++) { if (i) SP(); out_i32(a[i]); } NL(); } void out_u32_array(u32 *a, int a_len) { for (int i = 0; i < a_len; i++) { if (i) SP(); out_u32(a[i]); } NL(); } void out_i64_array(i64 *a, int a_len) { for (int i = 0; i < a_len; i++) { if (i) SP(); out_i64(a[i]); } NL(); } void out_u64_array(u64 *a, int a_len) { for (int i = 0; i < a_len; i++) { if (i) SP(); out_u64(a[i]); } NL(); } #pragma endregion io #pragma region hash map #define USED_LAST 16383 u64 m_used[1 << 14]; u64 m_keys[1 << 20]; u64 m_vals[1 << 20]; u64 r = 11995408973635179863ull; static inline void hash_init(void) { memset(m_used, 0, (1 << 14) * sizeof(u64)); memset(m_keys, 0, (1 << 20) * sizeof(u64)); memset(m_vals, 0, (1 << 20) * sizeof(u64)); } u32 hash(const u64 a) { return (u32)((a * r) >> 44); } bool test_bit(u32 i) { return (1ull) & (m_used[USED_LAST - (i / 64u)] >> (i % 64)); } void set_bit(u32 i) { m_used[USED_LAST - (i / 64)] |= (1ull << (i % 64)); } u64 get_value(u64 key) { for (u32 i = hash(key);; ++i, i &= 1048575) { if (!test_bit(i)) return 0; if (m_keys[i] == key) return m_vals[i]; } } void set_key_and_value(u64 key, u64 value) { for (u32 i = hash(key);; ++i, i &= 1048575) { if (!test_bit(i)) { set_bit(i); m_keys[i] = key; m_vals[i] = value; return; } if (m_keys[i] == key) { m_vals[i] = value; return; } } } #pragma endregion hash map void Main(void) { hash_init(); int T = read_int(); while (T--) { int op = read_int(); if (op == 0) { u64 k = in_u64(); u64 v = in_u64(); set_key_and_value(k, v); } else { u64 k = in_u64(); out_u64(get_value(k)); NL(); } } } int main(void) { Main(); return 0; }