#line 2 "marathon/top-k.hpp"
#include <algorithm>
#include <vector>
using namespace std ;
#line 2 "hashmap/hashmap-unerasable.hpp"
#include <cassert>
#include <chrono>
#include <functional>
#line 7 "hashmap/hashmap-unerasable.hpp"
using namespace std ;
#line 2 "internal/internal-hash-function.hpp"
#line 4 "internal/internal-hash-function.hpp"
using namespace std ;
#line 2 "internal/internal-seed.hpp"
#line 4 "internal/internal-seed.hpp"
using namespace std ;
namespace internal {
unsigned long long non_deterministic_seed () {
unsigned long long m =
chrono :: duration_cast < chrono :: nanoseconds > (
chrono :: high_resolution_clock :: now (). time_since_epoch ())
. count ();
m ^= 9845834732710364265uLL ;
m ^= m << 24 , m ^= m >> 31 , m ^= m << 35 ;
return m ;
}
unsigned long long deterministic_seed () { return 88172645463325252UL ; }
// 64 bit の seed 値を生成 (手元では seed 固定)
// 連続で呼び出すと同じ値が何度も返ってくるので注意
// #define RANDOMIZED_SEED するとシードがランダムになる
unsigned long long seed () {
#if defined(NyaanLocal) && !defined(RANDOMIZED_SEED)
return deterministic_seed ();
#else
return non_deterministic_seed ();
#endif
}
} // namespace internal
#line 2 "internal/internal-type-traits.hpp"
#include <type_traits>
using namespace std ;
namespace internal {
template < typename T >
using is_broadly_integral =
typename conditional_t < is_integral_v < T > || is_same_v < T , __int128_t > ||
is_same_v < T , __uint128_t > ,
true_type , false_type >:: type ;
template < typename T >
using is_broadly_signed =
typename conditional_t < is_signed_v < T > || is_same_v < T , __int128_t > ,
true_type , false_type >:: type ;
template < typename T >
using is_broadly_unsigned =
typename conditional_t < is_unsigned_v < T > || is_same_v < T , __uint128_t > ,
true_type , false_type >:: type ;
#define ENABLE_VALUE(x) \
template <typename T> \
constexpr bool x##_v = x<T>::value;
ENABLE_VALUE ( is_broadly_integral );
ENABLE_VALUE ( is_broadly_signed );
ENABLE_VALUE ( is_broadly_unsigned );
#undef ENABLE_VALUE
#define ENABLE_HAS_TYPE(var) \
template <class, class = void> \
struct has_##var : false_type {}; \
template <class T> \
struct has_##var<T, void_t<typename T::var>> : true_type {}; \
template <class T> \
constexpr auto has_##var##_v = has_##var<T>::value;
#define ENABLE_HAS_VAR(var) \
template <class, class = void> \
struct has_##var : false_type {}; \
template <class T> \
struct has_##var<T, void_t<decltype(T::var)>> : true_type {}; \
template <class T> \
constexpr auto has_##var##_v = has_##var<T>::value;
} // namespace internal
#line 8 "internal/internal-hash-function.hpp"
namespace internal {
// 整数, 整数列を 64 bit unsigned int へ移す
using u64 = unsigned long long ;
using u128 = __uint128_t ;
ENABLE_HAS_TYPE ( first_type );
ENABLE_HAS_TYPE ( second_type );
ENABLE_HAS_TYPE ( iterator );
template < typename T >
u64 hash_function ( const T & x ) {
static u64 r = seed ();
constexpr u64 z1 = 11995408973635179863ULL ;
if constexpr ( is_broadly_integral_v < T > ) {
// Integral
return ( u64 ( x ) ^ r ) * z1 ;
} else if constexpr ( has_first_type_v < T > && has_second_type_v < T > ) {
// pair
constexpr u64 z2 = 10150724397891781847ULL ;
return hash_function ( x . first ) + hash_function ( x . second ) * z2 ;
} else if constexpr ( has_iterator_v < T > ) {
// Container
constexpr u64 mod = ( 1LL << 61 ) - 1 ;
constexpr u64 base = 950699498548472943ULL ;
u64 m = 0 ;
for ( auto & z : x ) {
u64 w ;
if constexpr ( is_broadly_integral_v < T > ) {
w = u64 ( z ) ^ r ;
} else {
w = hash_function ( z );
}
u128 y = u128 ( m ) * base + ( w & mod );
m = ( y & mod ) + ( y >> 61 );
if ( m >= mod ) m -= mod ;
}
m ^= m << 24 , m ^= m >> 31 , m ^= m << 35 ;
return m ;
} else {
static_assert ([]() { return false ; }());
}
}
template < typename Key >
struct HashObject {
size_t operator ()( const Key & x ) const { return hash_function ( x ); }
};
} // namespace internal
/*
@brief ハッシュ関数
*/
#line 10 "hashmap/hashmap-unerasable.hpp"
// 削除不可能な hashmap
//
// テンプレート引数
// fixed_size : これを true にするするとバケットサイズが固定になる
// get_hash : ハッシュ関数の指定
// 引数
// _default_value : val の初期値, この値で初期化
// _default_size :
// バケットサイズ, max(4, _default_size) 以上の 2 べきで初期化
// ただし fixed_size が true の時にしかサイズを変更できない
template < typename Key , typename Val , bool fixed_size = false ,
unsigned long long ( * get_hash )( const Key & ) =
internal :: hash_function < Key > >
struct UnerasableHashMap {
int N , occupied_num , shift ;
vector < Key > keys ;
vector < Val > vals ;
vector < char > flag ;
Val default_value ;
int default_size ;
// サイズを n に変更する
void init ( int n , bool reset = false ) {
assert ( n >= 4 && ( n & ( n - 1 )) == 0 );
if constexpr ( fixed_size ) {
assert ( reset == true );
n = N ;
}
if ( reset == true ) {
N = n , occupied_num = 0 , shift = 64 - __builtin_ctz ( n );
keys . resize ( n );
vals . resize ( n );
flag . resize ( n );
fill ( begin ( vals ), end ( vals ), default_value );
fill ( begin ( flag ), end ( flag ), 0 );
} else {
N = n , shift = 64 - __builtin_ctz ( n );
vector < Key > keys2 ( n );
vector < Val > vals2 ( n , default_value );
vector < char > flag2 ( n );
swap ( keys , keys2 ), swap ( vals , vals2 ), swap ( flag , flag2 );
for ( int i = 0 ; i < ( int ) flag2 . size (); i ++ ) {
if ( flag2 [ i ]) {
int j = hint ( keys2 [ i ]);
keys [ j ] = keys2 [ i ], vals [ j ] = vals2 [ i ], flag [ j ] = 1 ;
}
}
}
}
UnerasableHashMap ( const Val & _default_value = Val {}, int _default_size = 4 )
: occupied_num ( 0 ), default_value ( _default_value ) {
if ( fixed_size == false ) _default_size = 4 ;
N = 4 ;
while ( N < _default_size ) N *= 2 ;
default_size = N ;
init ( N , true );
}
int hint ( const Key & k ) {
int hash = get_hash ( k ) >> shift ;
while ( flag [ hash ] && keys [ hash ] != k ) hash = ( hash + 1 ) & ( N - 1 );
return hash ;
}
// key が i である要素への参照を返す
Val & operator []( const Key & k ) {
int i = hint ( k );
if ( ! flag [ i ]) {
if constexpr ( fixed_size == false ) {
if ( occupied_num * 2 >= N ) {
init ( 2 * N ), i = hint ( k );
}
}
keys [ i ] = k , flag [ i ] = 1 , occupied_num ++ ;
}
return vals [ i ];
}
Val get ( const Key & k ) {
int i = hint ( k );
return flag [ i ] ? vals [ i ] : default_value ;
}
// 走査, f に関数 f(key, val) を入れる
template < typename F >
void enumerate ( const F f ) {
for ( int i = 0 ; i < ( int ) flag . size (); i ++ ) {
if ( flag [ i ]) f ( keys [ i ], vals [ i ]);
}
}
int count ( const Key & k ) { return flag [ hint ( k )]; }
bool contain ( const Key & k ) { return flag [ hint ( k )]; }
int size () const { return occupied_num ; }
void reset () { init ( default_size , true ); }
void clear () { init ( default_size , true ); }
};
#line 8 "marathon/top-k.hpp"
// コストの小さい順に K 個選ぶ
// hash が衝突したらコストの小さい方を選ぶ
//
// Data : bool operator< が定義されている必要がある
template < typename Data , unsigned long long ( * get_hash )( const Data & )>
struct Top_K {
int K ;
vector < Data > v ;
UnerasableHashMap < unsigned long long , int , true > mp ;
Top_K ( int k ) : K ( k ), mp ( - 1u , 2 * K ) {}
void normalize () {
if (( int ) v . size () < K ) return ;
nth_element ( begin ( v ), begin ( v ) + K , end ( v ));
v . resize ( K );
mp . clear ();
for ( int i = 0 ; i < K ; i ++ ) mp [ get_hash ( v [ i ])] = i ;
}
// d を挿入
void insert ( const Data & d ) {
unsigned long long ha = get_hash ( d );
int hint = mp . hint ( ha );
// 既に要素が存在する場合は何もしない
if ( mp . flag [ hint ]) {
int idx = mp . vals [ hint ];
if ( d < v [ idx ]) v [ idx ] = d ;
return ;
}
// v と map を更新する
v . push_back ( d );
mp . keys [ hint ] = ha ;
mp . vals [ hint ] = v . size () - 1 ;
mp . flag [ hint ] = 1 ;
mp . occupied_num ++ ;
if (( int ) v . size () >= 2 * K ) normalize ();
}
// 参照を返す
vector < Data >& get () {
normalize ();
return v ;
}
}; 
marathon/top-k.hpp
hashmap/hashmap-unerasable.hpp