This documentation is automatically generated by competitive-verifier/competitive-verifier
// @brief System of Linear Equations (Mod 2)
#define PROBLEM "https://judge.yosupo.jp/problem/system_of_linear_equations_mod_2"
#pragma GCC optimize("Ofast,unroll-loops")
#include "cp-algo/structures/bitpack.hpp"
#include <bits/stdc++.h>
using namespace std;
using cp_algo::structures::bitpack;
const int maxn = (1 << 12) + 1;
bitpack<maxn> a[maxn];
void solve() {
size_t n, m;
cin >> n >> m;
vector<string> As(n);
for(size_t i = 0; i < n; i++) {
cin >> As[i];
}
string bs;
cin >> bs;
for(size_t i = 0; i < n; i++) {
As[i] += bs[i];
a[i] = As[i];
}
vector<size_t> lead(n);
auto vars = views::iota((size_t)0, m + 1);
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] = a[i].ctz();
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]);
}
}
}
bitpack<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 << x[i].to_string().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();
}
}
#line 1 "verify/structures/bitpack/system_mod_2.test.cpp"
// @brief System of Linear Equations (Mod 2)
#define PROBLEM "https://judge.yosupo.jp/problem/system_of_linear_equations_mod_2"
#pragma GCC optimize("Ofast,unroll-loops")
#line 1 "cp-algo/structures/bitpack.hpp"
#line 1 "cp-algo/structures/bit_array.hpp"
#line 1 "cp-algo/util/bit.hpp"
#include <immintrin.h>
#include <cstdint>
#include <array>
#include <bit>
namespace cp_algo {
template<typename Uint>
constexpr size_t bit_width = sizeof(Uint) * 8;
size_t order_of_bit(auto x, size_t k) {
return k ? std::popcount(x << (bit_width<decltype(x)> - k)) : 0;
}
[[gnu::target("bmi2")]]
size_t kth_set_bit(uint64_t x, size_t k) {
return std::countr_zero(_pdep_u64(1ULL << k, x));
}
template<int fl = 0>
void with_bit_floor(size_t n, auto &&callback) {
if constexpr (fl >= 63) {
return;
} else if (n >> (fl + 1)) {
with_bit_floor<fl + 1>(n, callback);
} else {
callback.template operator()<1ULL << fl>();
}
}
}
#line 4 "cp-algo/structures/bit_array.hpp"
namespace cp_algo::structures {
template<size_t N, typename Uint = uint64_t>
struct bit_array {
static constexpr size_t width = bit_width<Uint>;
static constexpr size_t blocks = N / width + 1;
std::array<Uint, blocks> data = {};
uint64_t word(size_t x) const {
return data[x];
}
void set(size_t x) {
data[x / width] |= 1ULL << (x % width);
}
void flip(size_t x) {
data[x / width] ^= 1ULL << (x % width);
}
bool test(size_t x) const {
return (data[x / width] >> (x % width)) & 1;
}
bool operator[](size_t x) const {
return test(x);
}
};
}
#line 6 "cp-algo/structures/bitpack.hpp"
#include <cstddef>
#include <string>
#line 9 "cp-algo/structures/bitpack.hpp"
namespace cp_algo::structures {
template<size_t n, typename Int = uint64_t>
struct bitpack: bit_array<n, Int> {
using Base = bit_array<n, Int>;
using Base::width, Base::blocks, Base::data;
auto operator <=> (bitpack const& t) const = default;
bitpack() {}
bitpack(std::string bits) {
size_t rem = size(bits) % width;
if(rem) {
bits += std::string(width - rem, '0');
}
for(size_t i = 0, pos = 0; pos < size(bits); i++, pos += width) {
for(size_t j = width; j; j--) {
data[i] *= 2;
data[i] ^= bits[pos + j - 1] == '1';
}
}
}
bitpack& xor_hint(bitpack const& t, size_t hint) {
for(size_t i = hint / width; i < blocks; i++) {
data[i] ^= t.data[i];
}
return *this;
}
bitpack& operator ^= (bitpack const& t) {
return xor_hint(t, 0);
}
bitpack operator ^ (bitpack const& t) const {
return bitpack(*this) ^= t;
}
std::string to_string() const {
std::string res(blocks * width, '0');
for(size_t i = 0, pos = 0; i < blocks; i++, pos += width) {
Int block = data[i];
for(size_t j = 0; j < width; j++) {
res[pos + j] = '0' + block % 2;
block /= 2;
}
}
res.resize(n);
return res;
}
size_t ctz() const {
size_t res = 0;
size_t i = 0;
while(i < blocks && data[i] == 0) {
res += width;
i++;
}
if(i < blocks) {
res += std::countr_zero(data[i]);
}
return std::min(res, n);
}
};
}
#line 5 "verify/structures/bitpack/system_mod_2.test.cpp"
#include <bits/stdc++.h>
using namespace std;
using cp_algo::structures::bitpack;
const int maxn = (1 << 12) + 1;
bitpack<maxn> a[maxn];
void solve() {
size_t n, m;
cin >> n >> m;
vector<string> As(n);
for(size_t i = 0; i < n; i++) {
cin >> As[i];
}
string bs;
cin >> bs;
for(size_t i = 0; i < n; i++) {
As[i] += bs[i];
a[i] = As[i];
}
vector<size_t> lead(n);
auto vars = views::iota((size_t)0, m + 1);
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] = a[i].ctz();
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]);
}
}
}
bitpack<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 << x[i].to_string().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();
}
}
Env | Name | Status | Elapsed | Memory |
---|---|---|---|---|
g++ | example_00 | AC | 7 ms | 8 MB |
g++ | example_01 | AC | 7 ms | 8 MB |
g++ | example_02 | AC | 7 ms | 8 MB |
g++ | max_lowrank_00 | AC | 79 ms | 43 MB |
g++ | max_lowrank_01 | AC | 46 ms | 43 MB |
g++ | max_lowrank_02 | AC | 80 ms | 43 MB |
g++ | max_lowrank_03 | AC | 54 ms | 43 MB |
g++ | max_lowrank_04 | AC | 198 ms | 43 MB |
g++ | max_lowrank_05 | AC | 45 ms | 43 MB |
g++ | max_lowrank_06 | AC | 81 ms | 43 MB |
g++ | max_lowrank_07 | AC | 46 ms | 43 MB |
g++ | max_lowrank_08 | AC | 126 ms | 43 MB |
g++ | max_lowrank_09 | AC | 191 ms | 43 MB |
g++ | max_random_00 | AC | 198 ms | 43 MB |
g++ | max_random_01 | AC | 196 ms | 43 MB |
g++ | max_random_02 | AC | 197 ms | 43 MB |
g++ | max_random_03 | AC | 195 ms | 43 MB |
g++ | max_random_04 | AC | 196 ms | 43 MB |
g++ | max_small_00 | AC | 13 ms | 8 MB |
g++ | max_small_01 | AC | 6 ms | 8 MB |
g++ | random_00 | AC | 17 ms | 9 MB |
g++ | random_01 | AC | 30 ms | 9 MB |
g++ | random_02 | AC | 15 ms | 8 MB |
g++ | random_03 | AC | 33 ms | 16 MB |
g++ | random_04 | AC | 19 ms | 12 MB |
g++ | small_max_00 | AC | 37 ms | 8 MB |
g++ | small_max_01 | AC | 7 ms | 8 MB |
g++ | small_random_00 | AC | 7 ms | 8 MB |
g++ | small_random_01 | AC | 7 ms | 8 MB |
g++ | small_random_02 | AC | 7 ms | 8 MB |
g++ | small_random_03 | AC | 7 ms | 8 MB |
g++ | small_random_04 | AC | 7 ms | 8 MB |
g++ | smallest_00 | AC | 7 ms | 8 MB |
g++ | smallest_01 | AC | 7 ms | 8 MB |
g++ | smallest_02 | AC | 7 ms | 8 MB |
g++ | smallest_03 | AC | 7 ms | 8 MB |