test/aoj/1308/main.test.cpp
Depends on
Code
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1308"
#include <bitset>
#include <iostream>
#include <vector>
#include "Mylib/IO/input_vector.cpp"
#include "Mylib/LinearAlgebra/simultaneous_linear_equations_binary.cpp"
namespace hl = haar_lib;
int main() {
std::cin.tie(0);
std::ios::sync_with_stdio(false);
int m, n, d;
while (std::cin >> m >> n >> d, m) {
auto s = hl::input_vector<int>(n, m);
auto a = std::vector(n * m, std::bitset<25 * 25>());
std::vector<bool> b(n * m);
std::vector<std::vector<int>> p(n, std::vector<int>(m));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
p[i][j] = j + i * m;
}
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
b[p[i][j]] = s[i][j];
}
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
a[p[i][j]][p[i][j]] = 1;
for (int x = 0; x < n; ++x) {
for (int y = 0; y < m; ++y) {
if (abs(i - x) + abs(j - y) == d) {
a[p[x][y]][p[i][j]] = 1;
}
}
}
}
}
std::cout << (bool) (hl::binary_simultaneous_linear_equations(a, b)) << std::endl;
}
return 0;
}
#line 1 "test/aoj/1308/main.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1308"
#include <bitset>
#include <iostream>
#include <vector>
#line 4 "Mylib/IO/input_vector.cpp"
namespace haar_lib {
template <typename T>
std::vector<T> input_vector(int N) {
std::vector<T> ret(N);
for (int i = 0; i < N; ++i) std::cin >> ret[i];
return ret;
}
template <typename T>
std::vector<std::vector<T>> input_vector(int N, int M) {
std::vector<std::vector<T>> ret(N);
for (int i = 0; i < N; ++i) ret[i] = input_vector<T>(M);
return ret;
}
} // namespace haar_lib
#line 3 "Mylib/LinearAlgebra/simultaneous_linear_equations_binary.cpp"
#include <optional>
#include <utility>
#line 6 "Mylib/LinearAlgebra/simultaneous_linear_equations_binary.cpp"
namespace haar_lib {
namespace binary_simultaneous_linear_equations_impl {
template <size_t N>
struct result {
int rank, dim;
std::vector<bool> solution;
};
} // namespace binary_simultaneous_linear_equations_impl
template <size_t N>
auto binary_simultaneous_linear_equations(std::vector<std::bitset<N>> a, std::vector<bool> b) {
using result = binary_simultaneous_linear_equations_impl::result<N>;
std::optional<result> ret;
const int n = a.size(), m = N;
int rank = 0;
for (int j = 0; j < m; ++j) {
int pivot = -1;
for (int i = rank; i < n; ++i) {
if (a[i][j]) {
pivot = i;
break;
}
}
if (pivot == -1) continue;
std::swap(a[pivot], a[rank]);
swap(b[pivot], b[rank]);
for (int i = 0; i < n; ++i) {
if (i != rank and a[i][j]) {
a[i] ^= a[rank];
b[i] = b[i] ^ b[rank];
}
}
++rank;
}
for (int i = rank; i < n; ++i) {
if (b[i]) {
return ret;
}
}
const int dim = m - rank;
std::vector<bool> solution(m);
for (int i = 0; i < rank; ++i) solution[i] = b[i];
ret = result({rank, dim, solution});
return ret;
}
} // namespace haar_lib
#line 8 "test/aoj/1308/main.test.cpp"
namespace hl = haar_lib;
int main() {
std::cin.tie(0);
std::ios::sync_with_stdio(false);
int m, n, d;
while (std::cin >> m >> n >> d, m) {
auto s = hl::input_vector<int>(n, m);
auto a = std::vector(n * m, std::bitset<25 * 25>());
std::vector<bool> b(n * m);
std::vector<std::vector<int>> p(n, std::vector<int>(m));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
p[i][j] = j + i * m;
}
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
b[p[i][j]] = s[i][j];
}
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
a[p[i][j]][p[i][j]] = 1;
for (int x = 0; x < n; ++x) {
for (int y = 0; y < m; ++y) {
if (abs(i - x) + abs(j - y) == d) {
a[p[x][y]][p[i][j]] = 1;
}
}
}
}
}
std::cout << (bool) (hl::binary_simultaneous_linear_equations(a, b)) << std::endl;
}
return 0;
}
Back to top page