fork download
  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
stdin
1
stdout
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