gt22

Untitled

Sep 19th, 2020 (edited)
926
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <vector>
  2. #include <cmath>
  3. #include "optimization.h"
  4. #include <tuple>
  5. #include <bitset>
  6.  
  7. using namespace std;
  8. using ind = size_t;
  9.  
  10. constexpr int N = 202;
  11.  
  12.  
  13. struct Gauss {
  14.     vector<bitset<N>> A;
  15.     vector<int> col;
  16.     ind n, m;
  17.  
  18.     Gauss(ind n, ind m) : n(n), m(m) {}
  19.  
  20.     int add(bitset<N> a) {
  21.         for (ind i = 0; i < A.size(); ++i) {
  22.             if (a[col[i]]) {
  23.                 a ^= A[i];
  24.             }
  25.         }
  26.         ind i = 0;
  27.         while (i < n && !a[i]) i++;
  28.         if (i == n) return 0;
  29.         if(i == n - 1) return -1;
  30.         A.push_back(std::move(a));
  31.         col.push_back(i);
  32.         return 1;
  33.     }
  34.  
  35.     bitset<N> getX() {
  36.         ind k = A.size();
  37.         bitset<N> x;
  38.         for(int i = k - 1; i >= 0; i--) {
  39.             x[col[i]] = A[i][m];
  40.             for(ind j = i + 1; j < k; j++) {
  41.                 x[col[i]] = x[col[i]] ^ (A[i][col[j]] & x[col[j]]);
  42.             }
  43.         }
  44.         return x;
  45.     }
  46. };
  47.  
  48. int main() {
  49.     int n = readInt();
  50.     Gauss g(n + 1, n);
  51.     vector<bitset<N>> m(n);
  52.     for (int i = 0; i < n; ++i) {
  53.         int k = readInt();
  54.         for (int j = 0; j < k; ++j) {
  55.             int b = readInt() - 1;
  56.             m[b][i] = true;
  57.         }
  58.     }
  59.     for (int i = 0; i < n; ++i) {
  60.         m[i][n] = readInt() == 1;
  61.     }
  62.     for(auto& v : m) {
  63.         if(g.add(v) == -1) {
  64. //            writeInt(-1, '\n');
  65. //            return 0;
  66.         }
  67.     }
  68.     auto x = g.getX();
  69.     for(auto v : m) {
  70.         bool a = v[n];
  71.         for(int i = 0; i < n; i++) {
  72.             a ^= v[i] & x[i];
  73.         }
  74.         if(a != 0) {
  75.             writeInt(-1, '\n');
  76.             return 0;
  77.         }
  78.     }
  79.     writeInt(x.count(), '\n');
  80.     for (int i = 0; i < n; ++i) {
  81.         if(x[i]) {
  82.             writeInt(i + 1, ' ');
  83.         }
  84.     }
  85.     return 0;
  86. }
RAW Paste Data