fork download
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int N = 1024;
  6.  
  7. //---------------------------------------------------------------------------
  8. // An update to shuffle the random samples using algorithm::random_shuffle()
  9.  
  10. const int M=3;
  11.  
  12. int random_sample[M][N*N];
  13.  
  14. inline void shuffle_matrix(int p)
  15. {
  16. for(int i = 0; i < p; ++i)
  17. for(int r = rand(), m = 0; m < M; ++m)
  18. random_sample[m][i] = r;
  19.  
  20. random_shuffle(random_sample[1],random_sample[1]+p);
  21. }
  22.  
  23. using bits = bitset<N>;
  24. using matrix = bits[N];
  25. //---------------------------------------------------------------------------
  26.  
  27. int GetRank(matrix a[], int m, int n)
  28. {
  29. bits used;
  30.  
  31. for (int pivot, row, col = 0; col < n; ++col)
  32. {
  33. for (pivot = -1, row = 0; row < n; ++row)
  34. if (!used[row] && a[m][row][col])
  35. {
  36. pivot = row; break;
  37. }
  38.  
  39. if (pivot != -1)
  40. for(used[pivot] = true, row = 0; row < n; ++row)
  41. if (row != pivot and a[m][row][col])
  42. a[m][row] ^= a[m][pivot];
  43. }
  44.  
  45. return used.count();
  46. }
  47.  
  48. matrix a[M]; map<int,int> rank_reduction[M];
  49.  
  50. inline void generate_bit_matrix(int n)
  51. {
  52. for (int k = 0, i = 0; i < n; ++i)
  53. for (int j = 0; j < n; ++j, ++k)
  54. a[0][i][j] = random_sample[0][k] % 1000007 % 2,
  55. a[1][i][j] = random_sample[1][k] & 1,
  56. a[2][i][j] = random_sample[2][k] & 1;
  57. }
  58.  
  59. inline void compute_rank(int m, int n)
  60. {
  61. int p = GetRank(a,m,n), q = n-p;
  62.  
  63. rank_reduction[m][q]++;
  64. }
  65.  
  66. int main()
  67. {
  68. int l, r;
  69.  
  70. cin >> l >> r, assert(l >= 1 and l <= r and r <= N), srand(time(NULL));
  71.  
  72. for (int n = l; n < r; n++)
  73. shuffle_matrix(n*n),
  74. generate_bit_matrix(n),
  75. compute_rank(0,n),
  76. compute_rank(1,n),
  77. compute_rank(2,n);
  78.  
  79. const string method[] =
  80. { "With % operator", "With random_shuffle", "Original" };
  81.  
  82. cout << "rank_reduction(order-rank) summary:" << endl;
  83.  
  84. for(int m = 0; m < M; ++m)
  85. {
  86. cout << method[m] << endl;
  87.  
  88. for(auto p: rank_reduction[m])
  89. cout << p.first << ' ' << p.second << endl;
  90. }
  91. }
  92.  
Success #stdin #stdout 5.71s 27912KB
stdin
900 1000
stdout
rank_reduction(order-rank) summary:
With % operator
0 25
1 65
2 10
With random_shuffle
0 24
1 64
2 12
Original
374 1
376 1
378 1
380 1
382 1
384 1
386 1
388 1
390 1
392 1
394 1
396 1
398 1
400 1
402 1
404 2
406 2
408 2
410 2
412 2
414 2
416 2
418 2
420 2
422 2
424 2
426 2
428 2
430 2
432 2
434 2
436 2
438 2
440 2
442 2
444 2
446 2
448 2
450 2
452 2
454 2
456 2
458 2
460 2
462 2
464 2
466 2
468 2
470 2
472 2
474 1
476 1
478 1
480 1
482 1
484 1
486 1
488 1
490 1
492 1
494 1
496 1
498 1
500 1
502 1