fork(2) download
copy 
  1. #pragma GCC optimize("Ofast")
  2. #include <bits/stdc++.h>
  3. template<int n, typename T>
  4. int lowerBound(const T* __restrict arr, const T val) {
  5. 	if (n == 1) { return val > arr[0]; } 
  6. 	else {
  7. 		constexpr int mid = n / 2;
  8. 		if (val > arr[mid]) { return mid+lowerBound<n-mid, T>(arr+mid, val); }
  9. 		else { return lowerBound<mid, T>(arr,val); }
  10. 	}
  11. };
  12.  
  13. template<int n, typename T>
  14. int loserBound(const T* __restrict arr, const T val) {
  15.     return int(std::lower_bound(arr,arr+n,val)-arr);
  16. }
  17.  
  18. uint32_t xorshift32(uint32_t x) {
  19. 	x ^= x << 13;
  20. 	x ^= x >> 17;
  21. 	x ^= x << 5;
  22. 	return x;
  23. }
  24.  
  25. int main() {
  26. 	static uint32_t arr[1 << 20];
  27. 	uint32_t state = 111;
  28. 	for (int i = 0; i < (1 << 20); i++) { state = arr[i] = xorshift32(state); }
  29. 	std::sort(arr,arr+(1<<20));
  30. 	#define TEST(s, f) \
  31. 	{ \
  32. 		std::cout << s << std::endl; \
  33. 		int res = 0; \
  34. 		double tin = (double)clock(), tout; \
  35. 		uint32_t q = 123; \
  36. 		for (int i = 0; i < (1 << 23); i++) \
  37. 			res += f<1<<20>(&arr[0], q = xorshift32(q));\
  38. 		tout = (double)clock(); \
  39. 		std::cout << "time = " << (tout - tin) / CLOCKS_PER_SEC << "s, sum = " << res << std::endl; \
  40. 	}
  41. 	TEST("Testing std::lower_bound...", loserBound);
  42. 	TEST("Testing lowerBound...", lowerBound);
  43. 	return 0;
  44. }
Success #stdin #stdout 2.82s 7848KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Testing std::lower_bound...
time = 1.65804s, sum = -480952848
Testing lowerBound...
time = 1.08398s, sum = -480952848
https://ideone.com/2o21Iw
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

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!