Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <vector>
- #include <cmath>
- #include "optimization.h"
- #include <tuple>
- #include <bitset>
- using namespace std;
- using ind = size_t;
- constexpr int N = 202;
- struct Gauss {
- vector<bitset<N>> A;
- vector<int> col;
- ind n, m;
- Gauss(ind n, ind m) : n(n), m(m) {}
- int add(bitset<N> a) {
- for (ind i = 0; i < A.size(); ++i) {
- if (a[col[i]]) {
- a ^= A[i];
- }
- }
- ind i = 0;
- while (i < n && !a[i]) i++;
- if (i == n) return 0;
- if(i == n - 1) return -1;
- A.push_back(std::move(a));
- col.push_back(i);
- return 1;
- }
- bitset<N> getX() {
- ind k = A.size();
- bitset<N> x;
- for(int i = k - 1; i >= 0; i--) {
- x[col[i]] = A[i][m];
- for(ind j = i + 1; j < k; j++) {
- x[col[i]] = x[col[i]] ^ (A[i][col[j]] & x[col[j]]);
- }
- }
- return x;
- }
- };
- int main() {
- int n = readInt();
- Gauss g(n + 1, n);
- vector<bitset<N>> m(n);
- for (int i = 0; i < n; ++i) {
- int k = readInt();
- for (int j = 0; j < k; ++j) {
- int b = readInt() - 1;
- m[b][i] = true;
- }
- }
- for (int i = 0; i < n; ++i) {
- m[i][n] = readInt() == 1;
- }
- for(auto& v : m) {
- if(g.add(v) == -1) {
- // writeInt(-1, '\n');
- // return 0;
- }
- }
- auto x = g.getX();
- for(auto v : m) {
- bool a = v[n];
- for(int i = 0; i < n; i++) {
- a ^= v[i] & x[i];
- }
- if(a != 0) {
- writeInt(-1, '\n');
- return 0;
- }
- }
- writeInt(x.count(), '\n');
- for (int i = 0; i < n; ++i) {
- if(x[i]) {
- writeInt(i + 1, ' ');
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement