tests/yosupo/associative-array.test.cpp

• View this file on GitHub
• Last update: 2023-02-27 10:03:35-03:00
• Problem: https://judge.yosupo.jp/problem/associative_array

Depends on

• FastMap.cpp
• Template.cpp
• bits/stdc++.h

Code

#define PROBLEM "https://judge.yosupo.jp/problem/associative_array"
#include "Template.cpp"
#include "FastMap.cpp"

int32_t main() {
  iopt;

  lib::FastMap<int, int> st;

  int n; cin >> n;

  for(int i = 0; i < n; i++) {
    int t, k; cin >> t >> k;
    if (t == 0) {
      int v;
      cin >> v;
      st[k] = v;
    } else {
      cout << st[k] << endl;
    }
  }
}

#line 1 "tests/yosupo/associative-array.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/associative_array"
#line 1 "Template.cpp"
#include <bits/stdc++.h>
#define int long long
using namespace std;
 
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ms(v, x) memset((v), (x), sizeof(v))
#define all(v) (v).begin(), (v).end()
#define ff first
#define ss second
#define iopt ios::sync_with_stdio(false); cin.tie(0)
#define untie(p, a, b) decltype(p.first) a = p.first, decltype(p.second) b = p.second
#define TESTCASE(tn) cout << "Case #" << tn << ": "
 
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a%b); }

int floor2(int x, int y);
int ceil2(int x, int y) {
  if(y < 0) return ceil2(-x, -y);
  return x < 0 ? -floor2(-x, y) : (x + y - 1) / y;
}
int floor2(int x, int y) {
  if(y < 0) return floor2(-x, -y);
  return x < 0 ? -ceil2(-x, y) : x / y;
}
 
typedef pair<int, int> ii;
typedef long double LD;
typedef vector<int> vi;

#define TC_MAIN int32_t main() { iopt; int T; cin >> T; for(int i = 1; i <= T; i++) solve(i); }
#line 1 "FastMap.cpp"


#line 4 "FastMap.cpp"

// Pretty much copied from:
// https://nyaannyaan.github.io/library/data-structure/hash-map-variable-length.hpp
namespace lib {
using namespace std;

template <typename Key, typename Val = Key>
struct FastMap {
  using u32 = uint32_t;
  using u64 = uint64_t;

  u32 cap, s;
  vector<Key> keys;
  vector<Val> vals;
  vector<bool> flag;
  u64 r;
  u32 shift;
  Val DefaultValue;

  static u64 rng() {
    u64 m = chrono::duration_cast<chrono::nanoseconds>(
                chrono::high_resolution_clock::now().time_since_epoch())
                .count();
    m ^= m >> 16;
    m ^= m << 32;
    return m;
  }

  void reallocate() {
    cap <<= 1;
    vector<Key> k(cap);
    vector<Val> v(cap);
    vector<bool> f(cap);
    u32 sh = shift - 1;
    for (int i = 0; i < (int)flag.size(); i++) {
      if (flag[i]) {
        u32 hash = (u64(keys[i]) * r) >> sh;
        while (f[hash]) hash = (hash + 1) & (cap - 1);
        k[hash] = keys[i];
        v[hash] = vals[i];
        f[hash] = 1;
      }
    }
    keys.swap(k);
    vals.swap(v);
    flag.swap(f);
    --shift;
  }

  explicit FastMap()
      : cap(8),
        s(0),
        keys(cap),
        vals(cap),
        flag(cap),
        r(rng()),
        shift(64 - __lg(cap)),
        DefaultValue(Val()) {}

  Val& operator[](const Key& i) {
    u32 hash = (u64(i) * r) >> shift;
    while (true) {
      if (!flag[hash]) {
        if (s + s / 4 >= cap) {
          reallocate();
          return (*this)[i];
        }
        keys[hash] = i;
        flag[hash] = 1;
        ++s;
        return vals[hash] = DefaultValue;
      }
      if (keys[hash] == i) return vals[hash];
      hash = (hash + 1) & (cap - 1);
    }
  }

  // exist -> return pointer of Val
  // not exist -> return nullptr
  const Val* find(const Key& i) const {
    u32 hash = (u64(i) * r) >> shift;
    while (true) {
      if (!flag[hash]) return nullptr;
      if (keys[hash] == i) return &(vals[hash]);
      hash = (hash + 1) & (cap - 1);
    }
  }

  // return vector< pair<const Key&, val& > >
  vector<pair<Key, Val>> enumerate() const {
    vector<pair<Key, Val>> ret;
    for (u32 i = 0; i < cap; ++i)
      if (flag[i]) ret.emplace_back(keys[i], vals[i]);
    return ret;
  }

  int size() const { return s; }

  // set default_value
  void set_default(const Val& val) { DefaultValue = val; }
};
} // namespace lib


#line 4 "tests/yosupo/associative-array.test.cpp"

int32_t main() {
  iopt;

  lib::FastMap<int, int> st;

  int n; cin >> n;

  for(int i = 0; i < n; i++) {
    int t, k; cin >> t >> k;
    if (t == 0) {
      int v;
      cin >> v;
      st[k] = v;
    } else {
      cout << st[k] << endl;
    }
  }
}

Back to top page