CSES Problem Set - Distinct Numbers

#65da444ff0b947e697926a0e846907b2
2026.8.23
2026.8.23

  • 問題

  • 単純にunordered_setで集計したらTLEした

  • 調べてみると、テストケースがハッシュ衝突するように細工されているらしい

    • unordered_setは衝突すると挿入がO(n)に近づく

  • ハッシュ関数を実行時ランダム+Splitmix64に変えたらACできた

struct Splitmix64 {
  static uint64_t splitmix64(uint64_t x) {
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }

  size_t operator()(uint64_t x) const {
    static const uint64_t FIXED_RANDOM =
        std::chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x + FIXED_RANDOM);
  }
};

void answer() {
  llong n;
  read(n);
  std::unordered_set<llong, Splitmix64> x;

  for (llong i = 0; i < n; i++) {
    llong x_i;
    read(x_i);
    x.insert(x_i);
  }

  writeln(x.size());
}

参考