Advertisement
Guest User

Untitled

a guest
May 1st, 2016
59
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.16 KB | None | 0 0
  1. #pragma comment(linker, "/STACK:255000000")
  2. #include <vector>
  3. #include <iostream>
  4. #include <utility>
  5. #include <algorithm>
  6. #include <stack>
  7. #include <stdio.h>
  8. #include <math.h>
  9. #include <cstring>
  10. #include <tuple>
  11. #include <ctime>
  12. #include <climits>
  13. #include <cassert>
  14. #include <cstdio>
  15. #include <map>
  16. #include <iterator>
  17. #include <list>
  18. #include <set>
  19. #include <queue>
  20. #include <numeric>
  21. #include <bitset>
  22.  
  23. using namespace std;
  24.  
  25. const long long INFLL = LLONG_MAX;
  26. const long INF = LONG_MAX;
  27. const long N = 203;
  28.  
  29. void print_matr(vector < bitset<N> > a, int n)
  30. {
  31.     cout << "matr" << endl;
  32.     for (int i = 0; i < n; ++i)
  33.     {
  34.         for (int j = 0; j < n + 2; ++j)
  35.         {
  36.             cout << a[i][j] << " ";
  37.         }
  38.         cout << endl;
  39.     }
  40. }
  41.  
  42. long gauss(vector < bitset<N> > a, int n, int m, bitset<N> & ans)
  43. {
  44. //    print_matr(a, n);
  45.     vector<int> where(m, -1);
  46.     for (int col = 0, row = 0; col < m && row < n; ++col)
  47.     {
  48.         for (int i = row; i < n; ++i)
  49.             if (a[i][col])
  50.             {
  51.                 swap(a[i], a[row]);
  52.                 break;
  53.             }
  54.         if (!a[row][col])
  55.             continue;
  56.         where[col] = row;
  57.  
  58.         for (int i = 0; i < n; ++i)
  59.             if (i != row && a[i][col])
  60.                 a[i] ^= a[row];
  61.         ++row;
  62.     }
  63.  
  64.     for (int i = 0; i<m; ++i)
  65.         if (where[i] != -1)
  66.             ans[i] = a[where[i]][m] / a[where[i]][i];
  67.  
  68. //    print_matr(a, n);
  69. //    for (int i = 0; i < m; ++i)
  70. //    {
  71. //        cout << ans[i] << " ";
  72. //    }
  73. //    cout << endl;
  74.  
  75.     bool right_answer = true;
  76.     for (int i = 0; i<n; ++i) {
  77.         double sum = 0;
  78.         for (int j = 0; j<m; ++j)
  79.             sum += ans[j] * a[i][j];
  80.         if (abs(sum - a[i][m]) > 1e-10) {
  81.             right_answer = false;
  82.             break;
  83.         }
  84.     }
  85.  
  86.     if (!right_answer) {
  87.         for (int i = 0; i<n; ++i) {
  88.             double sum = 0;
  89.             for (int j = 0; j<m; ++j)
  90.                 sum += ans[j] * a[i][j];
  91.             if (abs(abs(sum - a[i][m]) - 1) > 1e-10) {
  92.                 return 0;
  93.             }
  94.         }
  95.     }
  96.     return 1;
  97.  
  98. //    for (int i = 0; i<m; ++i)
  99. //        if (where[i] == -1)
  100. //            return INF;
  101. //    return 1;
  102. }
  103.  
  104. int main()
  105. {
  106.     int n;
  107.     cin >> n;
  108.  
  109.     vector<bitset<N> > matr;
  110.     bitset<N> b;
  111.     matr.resize(n);
  112.  
  113.     int k, t;
  114.     for (int i = 0; i < n; ++i)
  115.     {
  116.         cin >> k;
  117.         for (int j = 0; j < k; ++j)
  118.         {
  119.             cin >> t;
  120.             matr[t-1][i] = 1;
  121.         }
  122.     }
  123.  
  124.     for (int i = 0; i < n; ++i)
  125.     {
  126.         cin >> t;
  127.         matr[i][n] = t;
  128.     }
  129.  
  130.     if (gauss(matr, n, n, b) != 1)
  131.     {
  132.  
  133.         for (int i = 0; i < n; ++i)
  134.         {
  135.             matr[i][n] = matr[i][n] ^ 1;
  136.         }
  137.         if (gauss(matr, n, n, b) != 1)
  138.         {
  139.             cout << -1 << endl;
  140.             return 0;
  141.         }
  142.     }
  143.     int L = 0;
  144.     for (int i = 0; i < n; ++i)
  145.     {
  146.         L += b[i];
  147.     }
  148.     cout << L << endl;
  149.  
  150.     for (int i = 0; i < n; ++i)
  151.     {
  152.         if (b[i])
  153.             cout << i + 1 << " ";
  154.     }
  155.     cout << endl;
  156.  
  157.     return 0;
  158. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement