Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma comment(linker, "/STACK:255000000")
- #include <vector>
- #include <iostream>
- #include <utility>
- #include <algorithm>
- #include <stack>
- #include <stdio.h>
- #include <math.h>
- #include <cstring>
- #include <tuple>
- #include <ctime>
- #include <climits>
- #include <cassert>
- #include <cstdio>
- #include <map>
- #include <iterator>
- #include <list>
- #include <set>
- #include <queue>
- #include <numeric>
- #include <bitset>
- using namespace std;
- const long long INFLL = LLONG_MAX;
- const long INF = LONG_MAX;
- const long N = 203;
- void print_matr(vector < bitset<N> > a, int n)
- {
- cout << "matr" << endl;
- for (int i = 0; i < n; ++i)
- {
- for (int j = 0; j < n + 2; ++j)
- {
- cout << a[i][j] << " ";
- }
- cout << endl;
- }
- }
- long gauss(vector < bitset<N> > a, int n, int m, bitset<N> & ans)
- {
- // print_matr(a, n);
- vector<int> where(m, -1);
- for (int col = 0, row = 0; col < m && row < n; ++col)
- {
- for (int i = row; i < n; ++i)
- if (a[i][col])
- {
- swap(a[i], a[row]);
- break;
- }
- if (!a[row][col])
- continue;
- where[col] = row;
- for (int i = 0; i < n; ++i)
- if (i != row && a[i][col])
- a[i] ^= a[row];
- ++row;
- }
- for (int i = 0; i<m; ++i)
- if (where[i] != -1)
- ans[i] = a[where[i]][m] / a[where[i]][i];
- // print_matr(a, n);
- // for (int i = 0; i < m; ++i)
- // {
- // cout << ans[i] << " ";
- // }
- // cout << endl;
- bool right_answer = true;
- for (int i = 0; i<n; ++i) {
- double sum = 0;
- for (int j = 0; j<m; ++j)
- sum += ans[j] * a[i][j];
- if (abs(sum - a[i][m]) > 1e-10) {
- right_answer = false;
- break;
- }
- }
- if (!right_answer) {
- for (int i = 0; i<n; ++i) {
- double sum = 0;
- for (int j = 0; j<m; ++j)
- sum += ans[j] * a[i][j];
- if (abs(abs(sum - a[i][m]) - 1) > 1e-10) {
- return 0;
- }
- }
- }
- return 1;
- // for (int i = 0; i<m; ++i)
- // if (where[i] == -1)
- // return INF;
- // return 1;
- }
- int main()
- {
- int n;
- cin >> n;
- vector<bitset<N> > matr;
- bitset<N> b;
- matr.resize(n);
- int k, t;
- for (int i = 0; i < n; ++i)
- {
- cin >> k;
- for (int j = 0; j < k; ++j)
- {
- cin >> t;
- matr[t-1][i] = 1;
- }
- }
- for (int i = 0; i < n; ++i)
- {
- cin >> t;
- matr[i][n] = t;
- }
- if (gauss(matr, n, n, b) != 1)
- {
- for (int i = 0; i < n; ++i)
- {
- matr[i][n] = matr[i][n] ^ 1;
- }
- if (gauss(matr, n, n, b) != 1)
- {
- cout << -1 << endl;
- return 0;
- }
- }
- int L = 0;
- for (int i = 0; i < n; ++i)
- {
- L += b[i];
- }
- cout << L << endl;
- for (int i = 0; i < n; ++i)
- {
- if (b[i])
- cout << i + 1 << " ";
- }
- cout << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement