fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. class custom_hash_t
  6. {
  7.     inline static uint64_t xor_shift( const uint64_t x, const int k )
  8.     {
  9.         return x ^ ( x >> k );
  10.     }
  11.  
  12.     inline static uint64_t xor_shift_multiply( const uint64_t x, const int k, const uint64_t y )
  13.     {
  14.         return xor_shift( x, k ) * y;
  15.     }
  16.  
  17.     inline static uint64_t splitmix64( uint64_t x )
  18.     {
  19.         /// http://x...content-available-to-author-only...i.it/splitmix64.c
  20.  
  21.         x += 0x9e3779b97f4a7c15,
  22.         x  = xor_shift_multiply( x, 30, 0xbf58476d1ce4e5b9 ),
  23.         x  = xor_shift_multiply( x, 27, 0x94d049bb133111eb );
  24.  
  25.         return xor_shift( x, 31 );
  26.     }
  27.  
  28. public:
  29.  
  30.     size_t operator()( uint64_t x ) const
  31.     {
  32.         static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
  33.  
  34.         return splitmix64( x + FIXED_RANDOM );
  35.     }
  36. };
  37.  
  38. #define SAFE_SET( STL, KEY         ) typedef unordered_##STL< KEY,         custom_hash_t > safe_##STL
  39. #define SAFE_MAP( STL, KEY, Mapped ) typedef unordered_##STL< KEY, Mapped, custom_hash_t > safe_##STL
  40.  
  41. typedef long long ll;
  42.  
  43. SAFE_SET(      set, ll );
  44. SAFE_SET( multiset, ll );
  45. SAFE_MAP(      map, ll, int );
  46. SAFE_MAP( multimap, ll, int );
  47.  
  48. #include <ext/pb_ds/assoc_container.hpp>
  49.  
  50. using namespace __gnu_pbds;
  51.  
  52. gp_hash_table< ll, int, custom_hash_t > safe_gp_hash_table;
  53.  
  54. #ifdef ONLINE_JUDGE
  55. #undef ONLINE_JUDGE
  56. #endif // ONLINE_JUDGE
  57.  
  58. /// The time_mointor() code starts here
  59. inline void time_monitor( const string& s, const function< void() >& procedure )
  60. {
  61. #ifndef ONLINE_JUDGE
  62.     typedef chrono::high_resolution_clock clock_t;
  63.  
  64.     auto start_time  = clock_t::now();
  65. #endif // ONLINE_JUDGE
  66.  
  67.     procedure();
  68.  
  69. #ifndef ONLINE_JUDGE
  70.     auto duration = clock_t::now() - start_time;
  71.  
  72.     typedef chrono::milliseconds time_scale;
  73.  
  74.     auto elapsed_time = chrono::duration_cast< time_scale >( duration ).count();
  75.  
  76.     cout << "void " << s << "() used " << elapsed_time << " ms\n";
  77. #endif // ONLINE_JUDGE
  78. }
  79.  
  80. #define time__( procedure ) time_monitor( #procedure, procedure )
  81.  
  82. /// The time_mointor() code ends here
  83.  
  84. template< class T >
  85. void insert_numbers( const ll x )
  86. {
  87.     T numbers; ll w = x, sum = 0;
  88.  
  89.     for ( size_t i = 1, N = 2e5; i <= N; i++ )
  90.         numbers[ w ] = i, w += x;
  91.  
  92.     for ( auto p : numbers )
  93.         sum += ( p.first / x ) * p.second;
  94.  
  95.     cout << "x = " << x << ": sum = " << sum << endl;
  96. }
  97.  
  98. typedef unordered_map< ll, int > unsafe_map;
  99.  
  100. int main()
  101. {
  102.     ios_base::sync_with_stdio( false ), cin.tie( nullptr ), cout.tie( nullptr );
  103.  
  104.     int safe; cin >> safe;
  105.  
  106.     if ( safe )
  107.         time__( []() { insert_numbers< safe_map >( 107897 ); } ),
  108.         time__( []() { insert_numbers< safe_map >( 126271 ); } );
  109.     else
  110.         time__( []() { insert_numbers< unsafe_map >( 107897 ); } ),
  111.         time__( []() { insert_numbers< unsafe_map >( 126271 ); } );
  112. }
Success #stdin #stdout 0.13s 15384KB
comments (?)
stdin
copy 
1
stdout
copy 
x = 107897: sum = 2666686666700000
void []() { insert_numbers< safe_map >( 107897 ); }() used 65 ms
x = 126271: sum = 2666686666700000
void []() { insert_numbers< safe_map >( 126271 ); }() used 69 ms
https://ideone.com/lB1QWL
safe_map
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!