System of Linear Equations (Mod 2) (verify/structures/bitpack/system_mod_2.test.cpp)

• View this file on GitHub
• Last update: 2025-12-17 02:23:31+01:00
• Problem: https://judge.yosupo.jp/problem/system_of_linear_equations_mod_2

Depends on

• cp-algo/structures/bit_array.hpp
• cp-algo/structures/bit_array_util.hpp
• cp-algo/util/big_alloc.hpp
• cp-algo/util/bit.hpp
• cp-algo/util/simd.hpp

Code

// @brief System of Linear Equations (Mod 2)
#define PROBLEM "https://judge.yosupo.jp/problem/system_of_linear_equations_mod_2"
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#include "cp-algo/structures/bit_array_util.hpp"
#include <bits/stdc++.h>

using namespace std;
using namespace cp_algo::structures;

const int maxn = (1 << 12) + 1;
bit_array<maxn> a[maxn];

void solve() {
    size_t n, m;
    cin >> n >> m;
    cp_algo::big_vector<cp_algo::big_string> As(n);
    for(size_t i = 0; i < n; i++) {
        cin >> As[i];
    }
    cp_algo::big_string bs;
    cin >> bs;
    for(size_t i = 0; i < n; i++) {
        As[i] += bs[i];
        from_string(a[i], As[i]);
    }
    cp_algo::big_vector<size_t> lead(n);
    auto vars = views::iota((size_t)0, m + 1);
    cp_algo::big_set<size_t> free(begin(vars), end(vars));
    for(size_t i = 0; i < n; i++) {
        for(size_t j = 0; j < i; j++) {
            if(a[i][lead[j]]) {
                a[i].xor_hint(a[j], lead[j]);
            }
        }
        lead[i] = ctz(a[i]);
        if(lead[i] == m) {
            cout << -1 << "\n";
            return;
        }
        if(lead[i] > m) {
            continue;
        }
        free.erase(lead[i]);
        for(size_t j = 0; j < i; j++) {
            if(a[j][lead[i]]) {
                a[j].xor_hint(a[i], lead[i]);
            }
        }
    }
    bit_array<maxn> x[maxn];
    for(auto [j, pj]: views::enumerate(free)) {
        x[j].set(pj);
        for(size_t i = 0; i < n; i++) {
            if(lead[i] < m && a[i][pj]) {
                x[j].set(lead[i]);
            }
        }
    }
    size_t rk = size(free) - 1;
    swap(x[0], x[rk]);
    cout << rk << "\n";
    for(size_t i = 0; i <= rk; i++) {
        cout << to_string(x[i]).substr(0, m) << "\n";
    }
}

signed main() {
    //freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    while(t--) {
        solve();
    }
}

Traceback (most recent call last):
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj_resolve/resolver.py", line 181, in resolve
    bundled_code = language.bundle(path, basedir=basedir)
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus.py", line 252, in bundle
    bundler.update(path)
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 327, in update
    assert len(lines) == len(uncommented_lines)
           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
AssertionError

Test cases

Env	Name	Status	Elapsed	Memory
g++	example_00	AC	7 ms	6 MB
g++	example_01	AC	6 ms	6 MB
g++	example_02	AC	6 ms	6 MB
g++	max_lowrank_00	AC	263 ms	42 MB
g++	max_lowrank_01	AC	74 ms	42 MB
g++	max_lowrank_02	AC	112 ms	42 MB
g++	max_lowrank_03	AC	93 ms	42 MB
g++	max_lowrank_04	AC	326 ms	42 MB
g++	max_lowrank_05	AC	74 ms	42 MB
g++	max_lowrank_06	AC	102 ms	42 MB
g++	max_lowrank_07	AC	74 ms	42 MB
g++	max_lowrank_08	AC	183 ms	42 MB
g++	max_lowrank_09	AC	317 ms	42 MB
g++	max_random_00	AC	327 ms	42 MB
g++	max_random_01	AC	328 ms	42 MB
g++	max_random_02	AC	327 ms	42 MB
g++	max_random_03	AC	331 ms	42 MB
g++	max_random_04	AC	327 ms	42 MB
g++	max_small_00	AC	14 ms	8 MB
g++	max_small_01	AC	8 ms	9 MB
g++	random_00	AC	17 ms	8 MB
g++	random_01	AC	20 ms	7 MB
g++	random_02	AC	9 ms	7 MB
g++	random_03	AC	37 ms	14 MB
g++	random_04	AC	20 ms	10 MB
g++	small_max_00	AC	20 ms	6 MB
g++	small_max_01	AC	7 ms	7 MB
g++	small_random_00	AC	6 ms	6 MB
g++	small_random_01	AC	6 ms	6 MB
g++	small_random_02	AC	6 ms	6 MB
g++	small_random_03	AC	6 ms	6 MB
g++	small_random_04	AC	6 ms	6 MB
g++	smallest_00	AC	6 ms	6 MB
g++	smallest_01	AC	6 ms	6 MB
g++	smallest_02	AC	6 ms	6 MB
g++	smallest_03	AC	6 ms	6 MB

Back to top page