#include <bits/stdc++.h>
using namespace std;
const int N = 1024;
//---------------------------------------------------------------------------
// An update to shuffle the random samples using algorithm::random_shuffle()
const int M=3;
int random_sample[M][N*N];
inline void shuffle_matrix(int p)
{
for(int i = 0; i < p; ++i)
for(int r = rand(), m = 0; m < M; ++m)
random_sample[m][i] = r;
random_shuffle(random_sample[1],random_sample[1]+p);
}
using bits = bitset<N>;
using matrix = bits[N];
//---------------------------------------------------------------------------
int GetRank(matrix a[], int m, int n)
{
bits used;
for (int pivot, row, col = 0; col < n; ++col)
{
for (pivot = -1, row = 0; row < n; ++row)
if (!used[row] && a[m][row][col])
{
pivot = row; break;
}
if (pivot != -1)
for(used[pivot] = true, row = 0; row < n; ++row)
if (row != pivot and a[m][row][col])
a[m][row] ^= a[m][pivot];
}
return used.count();
}
matrix a[M]; map<int,int> rank_reduction[M];
inline void generate_bit_matrix(int n)
{
for (int k = 0, i = 0; i < n; ++i)
for (int j = 0; j < n; ++j, ++k)
a[0][i][j] = random_sample[0][k] % 1000007 % 2,
a[1][i][j] = random_sample[1][k] & 1,
a[2][i][j] = random_sample[2][k] & 1;
}
inline void compute_rank(int m, int n)
{
int p = GetRank(a,m,n), q = n-p;
rank_reduction[m][q]++;
}
int main()
{
int l, r;
cin >> l >> r, assert(l >= 1 and l <= r and r <= N), srand(time(NULL));
for (int n = l; n < r; n++)
shuffle_matrix(n*n),
generate_bit_matrix(n),
compute_rank(0,n),
compute_rank(1,n),
compute_rank(2,n);
const string method[] =
{ "With % operator", "With random_shuffle", "Original" };
cout << "rank_reduction(order-rank) summary:" << endl;
for(int m = 0; m < M; ++m)
{
cout << method[m] << endl;
for(auto p: rank_reduction[m])
cout << p.first << ' ' << p.second << endl;
}
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CiAKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKIApjb25zdCBpbnQgTiA9IDEwMjQ7CgovLy0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLQovLyBBbiB1cGRhdGUgdG8gc2h1ZmZsZSB0aGUgcmFuZG9tIHNhbXBsZXMgdXNpbmcgYWxnb3JpdGhtOjpyYW5kb21fc2h1ZmZsZSgpCgpjb25zdCBpbnQgTT0zOwoKaW50IHJhbmRvbV9zYW1wbGVbTV1bTipOXTsgCgppbmxpbmUgdm9pZCBzaHVmZmxlX21hdHJpeChpbnQgcCkKewogICAgZm9yKGludCBpID0gMDsgaSA8IHA7ICsraSkKICAgIAlmb3IoaW50IHIgPSByYW5kKCksIG0gPSAwOyBtIDwgTTsgKyttKQogICAgCQlyYW5kb21fc2FtcGxlW21dW2ldID0gcjsKICAgIAkKICAgIHJhbmRvbV9zaHVmZmxlKHJhbmRvbV9zYW1wbGVbMV0scmFuZG9tX3NhbXBsZVsxXStwKTsKfQoKdXNpbmcgYml0cyAgID0gYml0c2V0PE4+OyAKdXNpbmcgbWF0cml4ID0gICBiaXRzW05dOyAKLy8tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0KCmludCBHZXRSYW5rKG1hdHJpeCBhW10sIGludCBtLCBpbnQgbikgCnsKCWJpdHMgdXNlZDsKCQoJZm9yIChpbnQgcGl2b3QsIHJvdywgY29sID0gMDsgY29sIDwgbjsgKytjb2wpIAoJewogICAgCWZvciAocGl2b3QgPSAtMSwgcm93ID0gMDsgcm93IDwgbjsgKytyb3cpIAogICAgCQlpZiAoIXVzZWRbcm93XSAmJiBhW21dW3Jvd11bY29sXSkgCiAgICAJCXsKICAgICAgICAJCXBpdm90ID0gcm93OyBicmVhazsKICAgIAkJfQogICAKICAgIAlpZiAocGl2b3QgIT0gLTEpIAogICAgCQlmb3IodXNlZFtwaXZvdF0gPSB0cnVlLCByb3cgPSAwOyByb3cgPCBuOyArK3JvdykKICAgIAkJCWlmIChyb3cgIT0gcGl2b3QgYW5kIGFbbV1bcm93XVtjb2xdKSAKICAgIAkJCQlhW21dW3Jvd10gXj0gYVttXVtwaXZvdF07Cgl9CgkKCXJldHVybiB1c2VkLmNvdW50KCk7Cn0KIAptYXRyaXggYVtNXTsgbWFwPGludCxpbnQ+IHJhbmtfcmVkdWN0aW9uW01dOwoKaW5saW5lIHZvaWQgZ2VuZXJhdGVfYml0X21hdHJpeChpbnQgbikKewogICAgZm9yIChpbnQgayA9IDAsIGkgPSAwOyBpIDwgbjsgKytpKSAKICAgIAlmb3IgKGludCBqID0gMDsgaiA8IG47ICsraiwgKytrKSAKICAgICAgICAJYVswXVtpXVtqXSA9IHJhbmRvbV9zYW1wbGVbMF1ba10gJSAxMDAwMDA3ICUgMiwKICAgICAgICAJYVsxXVtpXVtqXSA9IHJhbmRvbV9zYW1wbGVbMV1ba10gJiAxLAogICAgICAgIAlhWzJdW2ldW2pdID0gcmFuZG9tX3NhbXBsZVsyXVtrXSAmIDE7Cn0KCmlubGluZSB2b2lkIGNvbXB1dGVfcmFuayhpbnQgbSwgaW50IG4pCnsKCWludCBwID0gR2V0UmFuayhhLG0sbiksIHEgPSBuLXA7CgkKCXJhbmtfcmVkdWN0aW9uW21dW3FdKys7Cn0KCmludCBtYWluKCkgCnsKCWludCBsLCByOyAKCQoJY2luID4+IGwgPj4gciwgYXNzZXJ0KGwgPj0gMSBhbmQgbCA8PSByIGFuZCByIDw9IE4pLCBzcmFuZCh0aW1lKE5VTEwpKTsKCQoJZm9yIChpbnQgbiA9IGw7IG4gPCByOyBuKyspCgkJc2h1ZmZsZV9tYXRyaXgobipuKSwKCQlnZW5lcmF0ZV9iaXRfbWF0cml4KG4pLAoJCWNvbXB1dGVfcmFuaygwLG4pLAoJCWNvbXB1dGVfcmFuaygxLG4pLAoJCWNvbXB1dGVfcmFuaygyLG4pOwoJCQoJY29uc3Qgc3RyaW5nIG1ldGhvZFtdID0gCgkJeyAiV2l0aCAlIG9wZXJhdG9yIiwgIldpdGggcmFuZG9tX3NodWZmbGUiLCAiT3JpZ2luYWwiIH07CgkJCgljb3V0IDw8ICJyYW5rX3JlZHVjdGlvbihvcmRlci1yYW5rKSBzdW1tYXJ5OiIgPDwgZW5kbDsKCQoJZm9yKGludCBtID0gMDsgbSA8IE07ICsrbSkKCXsJCgkJY291dCA8PCBtZXRob2RbbV0gPDwgZW5kbDsgCgkJCgkJZm9yKGF1dG8gcDogcmFua19yZWR1Y3Rpb25bbV0pCgkJCWNvdXQgPDwgcC5maXJzdCA8PCAnICcgPDwgcC5zZWNvbmQgPDwgZW5kbDsgCgl9Cn0K