fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using namespace chrono;
  4. using bvec = vector<bool>;
  5. const int N = 10000, E = 100;
  6.  
  7. class timer: high_resolution_clock {
  8.     time_point start_time;
  9. public:
  10.     inline timer () : start_time (now ()) {}
  11.     inline rep elapsed_time() const { 
  12.     	return duration_cast<milliseconds> (now () - start_time).count (); } };
  13.  
  14. inline int random_value(int min, int max) {
  15. 	static mt19937_64 random(system_clock::now().time_since_epoch().count()); 
  16.     return uniform_int_distribution<int>(min,max)(random); }
  17.  
  18. struct random_positions: bvec {
  19. 	inline random_positions(int n) : bvec(N+1,false) {
  20. 		for (int x, count = 0; count < n; )
  21. 			if (x = random_value(1,N), not at(x))
  22. 				at(x) = true, ++count; } };
  23.  
  24. struct ivec: vector<int> {
  25. 	ivec(int n) {
  26. 		const random_positions used(n); 
  27. 		resize(n);
  28. 		for (int i = 1, j = 0; i <= N and j < n; ++i)
  29. 			if (used[i])
  30. 				at(j++) = i; } };
  31.  
  32. struct distinct_distances: bvec {
  33. 	int elapsed_time; const int n, m;
  34. 	inline distinct_distances(const ivec &a) : n(a.size()), m(a.back()-a.front()) { resize(m+1,false); } };
  35.  
  36. struct unbounded: distinct_distances {
  37. 	inline unbounded(const ivec &a) : distinct_distances(a) {
  38. 		timer t;
  39.     	for (int j = n-1; j > 0; --j)
  40.         	for (int e = a[j], i = 0; i < j; ++i)
  41.         		at(e-a[i]) = true; 
  42.         elapsed_time = t.elapsed_time(); } };
  43.  
  44. struct bounded: distinct_distances {
  45. 	inline bounded(const ivec &a) : distinct_distances(a) {
  46. 		timer t;
  47. 		for (int count = 0, j = n-1; j > 0 and count < m; --j)
  48.         	for (int d, e = a[j], i = 0; i < j and count < m; ++i)
  49.         		if (d = e-a[i], not at(d))
  50.         			at(d) = true, ++count; 
  51.         elapsed_time = t.elapsed_time(); } };
  52.  
  53. inline void write(const string &prompt, int time) { cout << prompt << " Time = " << time << " msec." << endl; }
  54.  
  55. int main() {
  56. 	int t1 = 0, t2 = 0;
  57. 	for (int e = 0; e < E; ++e) {
  58. 		const int n = random_value(1,N); 
  59. 		const ivec a(n);
  60. 		const unbounded s(a); const bounded t(a);
  61. 		if (t1 += s.elapsed_time, t2 += t.elapsed_time, s != t)
  62. 			throw logic_error("Distinct distances are not equal"); }
  63. 	write("Unbounded",t1), 
  64. 	write("  Bounded",t2); }
  65.  
Success #stdin #stdout 3.32s 4380KB
comments (?)
stdin 
Standard input is empty
stdout 
Unbounded Time = 2937 msec.
  Bounded Time = 296 msec.
https://ideone.com/lUtJUB
language:
C++14 (gcc 8.3)
created:
5 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!