test/yosupo/associative_array_amt.test.cpp

View this file on GitHub
Last update: 2023-07-03 22:03:29+09:00
Problem: https://judge.yosupo.jp/problem/associative_array

Depends on

Code

#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;
}