fork download
copy 
  1. #include <vector>
  2. #include <bitset>
  3. #include <iostream>
  4.  
  5. using namespace std;
  6.  
  7. const int N = 2048;
  8.  
  9. int GetRank(vector<bitset<N>> matrix) {
  10.     const int n = matrix.size();
  11.     int r = 0;
  12.     vector<bool> used(n);
  13.  
  14.     for (int col = 0; col < n; ++col) {
  15.         int pivot = -1;
  16.         for (int row = 0; row < n; ++row) {
  17.             if (!used[row] && matrix[row][col]) {
  18.                 pivot = row; break;
  19.             }
  20.         }
  21.  
  22.         if (pivot == -1) { continue; }
  23.         used[pivot] = true;
  24.         ++r;
  25.  
  26.         for (int r = 0; r < n; ++r) {
  27.             if (r == pivot) { continue; }
  28.             if (matrix[r][col]) {
  29.                 matrix[r] ^= matrix[pivot];
  30.             }
  31.         }
  32.     }
  33.     return r;
  34. }
  35.  
  36. uint64_t xorshift64(uint64_t* state)
  37. {
  38.     uint64_t x = *state;
  39.     x^= x << 13;
  40.     x^= x >> 7;
  41.     x^= x << 17;
  42.     *state = x;
  43.     return x;
  44. }
  45.  
  46. #include <random>
  47. int main() {
  48.     int n=1900;
  49.  
  50.     mt19937 mt(time(NULL));
  51.     for (int i = 0; i < 10; ++i) {
  52.         int m = n + i;
  53.         vector<bitset<N>> matrix(m);
  54.         for (int i = 0; i < m; ++i) {
  55.             for (int j = 0; j < m; ++j) {
  56.                 matrix[i][j] = mt() % 2;
  57.             }
  58.         }
  59.  
  60.         cout << m << " "<< GetRank(matrix) << "\n";
  61.     }
  62. }
  63.  
Success #stdin #stdout 0.78s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1900 1899
1901 1900
1902 1901
1903 1903
1904 1904
1905 1905
1906 1906
1907 1907
1908 1908
1909 1908
https://ideone.com/8ueYut
language:
C++14 (gcc 8.3)
created:
5 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!