test/misc/inthash.test.cpp

• View this file on GitHub
• Last update: 2025-09-28 19:03:15+08:00
• Problem: https://judge.yosupo.jp/problem/associative_array

Depends on

• src/misc/inthash.hpp
• src/misc/read.hpp

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/associative_array
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#include "../../src/misc/inthash.hpp"
#include "../../src/misc/read.hpp"

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int q = read();
  unordered_map<ll, ll, IntHash> mp;
  while (q--) {
    int op = read();
    if (op == 0) {
      ll k = read(), v = read();
      mp[k] = v;
    } else if (op == 1) {
      ll k = read();
      cout << mp[k] << "\n";
    }
  }
  return 0;
}

#line 1 "test/misc/inthash.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/associative_array
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#line 1 "src/misc/inthash.hpp"
struct IntHash {
  // http://xorshift.di.unimi.it/splitmix64.c
  static uint64_t hash(uint64_t x) {
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }
  inline static const uint64_t SEED =
      chrono::steady_clock::now().time_since_epoch().count();
  size_t operator()(uint64_t x) const { return hash(x + SEED); }
  size_t operator()(pair<uint64_t, uint64_t> x) const {
    return hash(x.first + SEED) ^ (hash(x.second + SEED) >> 1);
  }
};
#line 1 "src/misc/read.hpp"
#define GC ch = getchar_unlocked()
ll read() {
  ll x = 0, f = 1, GC;
  while (ch < '0' || ch > '9') ch == '-' ? f = -1, GC : GC;
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', GC;
  return x * f;
}
#undef GC
#line 8 "test/misc/inthash.test.cpp"

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int q = read();
  unordered_map<ll, ll, IntHash> mp;
  while (q--) {
    int op = read();
    if (op == 0) {
      ll k = read(), v = read();
      mp[k] = v;
    } else if (op == 1) {
      ll k = read();
      cout << mp[k] << "\n";
    }
  }
  return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	2_powers_00	AC	368 ms	62 MB
g++	c_sharp_killer_00	AC	185 ms	37 MB
g++	example_00	AC	5 ms	4 MB
g++	many_0set_00	AC	206 ms	28 MB
g++	many_0set_sparse_00	AC	39 ms	4 MB
g++	max_many_updates_00	AC	352 ms	61 MB
g++	max_random_00	AC	207 ms	28 MB
g++	max_random_01	AC	222 ms	28 MB
g++	max_random_02	AC	280 ms	31 MB
g++	py_killer_00	AC	281 ms	54 MB
g++	py_killer_01	AC	306 ms	54 MB
g++	random_00	AC	88 ms	18 MB
g++	random_01	AC	108 ms	19 MB
g++	random_02	AC	136 ms	29 MB
g++	sparse_keys_00	AC	39 ms	4 MB
g++	sparse_keys_01	AC	45 ms	4 MB
g++	unordered_map_killer_00	AC	362 ms	62 MB
g++	unordered_map_killer_01	AC	408 ms	62 MB
g++	unordered_map_killer_02	AC	353 ms	62 MB
g++	unordered_map_killer_03	AC	370 ms	62 MB

Back to top page