SHARE
TWEET

Untitled

a guest Dec 16th, 2019 73 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define dbg() cerr <<
  3. #define name(x) (#x) << ": " << (x) << ' ' <<
  4.  
  5. using namespace std;
  6.  
  7. void Gauss(int n, vector<bitset<1024>> &eq) {
  8.   int i = 0, j = 0;
  9.   vector<int> row_idx(n, -1);
  10.   while (i < (int)eq.size() && j < n) {
  11.     bool cont = true;
  12.     for (int k = j; k < (int)eq.size(); ++k) {
  13.       if (eq[k][j]) {
  14.         swap(eq[i], eq[k]);
  15.         cont = false;
  16.       }
  17.     }
  18.     if (cont) {
  19.       ++j;
  20.       continue;
  21.     }
  22.     row_idx[j] = i;
  23.     for (int k = 0; k < (int)eq.size(); ++k) {
  24.       if (eq[k][j]) {
  25.         eq[k] ^= eq[i];
  26.       }
  27.     }
  28.     ++i, ++j;
  29.   }
  30.   vector<int> ans(n, -1);
  31.   for (int i = 0; i < n; ++i) {
  32.     if (row_idx[i] != -1) {
  33.       ans[i] = eq[row_idx[i]][n];
  34.     } else {
  35.       ans[i] = 1;
  36.     }
  37.   }
  38.   for (int i = 0; i < (int)eq.size(); ++i) {
  39.     for (int j = 0; j < n; ++j) {
  40.       eq[i][n] = eq[i][j] ^ (ans[j] & eq[i][j]);
  41.     }
  42.     if (eq[i][n]) {
  43.       cout << "impossible\n";
  44.       return;
  45.     }
  46.   }
  47.   for (int i = n - 1; i >= 0; --i) {
  48.     cout << (ans[i] ? 'T' : 'F');
  49.   }
  50.   cout << endl;
  51. }
  52.  
  53. int main() {
  54.   ios::sync_with_stdio(false);
  55.   cin.tie(0), cout.tie(0);
  56.  
  57.   int m, n; cin >> m >> n; cin.get();
  58.   vector<bitset<1024>> eq(m);
  59.   for (int i = 0; i < m; ++i) {
  60.     string s; getline(cin, s);
  61.     int pos = 0;
  62.     auto GetVar = [&]() {
  63.       bool neg = false;
  64.       if (s[pos] == 'n') {
  65.         assert(s[pos + 1] == 'o' && s[pos + 2] == 't');
  66.         pos += 4;
  67.         neg = true;
  68.       }
  69.       dbg() name(s) name(pos) endl;
  70.       assert(s[pos++] == 'x');
  71.       int num = 0;
  72.       while (isdigit(s[pos])) {
  73.         num = (num << 1) + (num << 3) + s[pos++] - '0';
  74.       }
  75.       while (s[pos++] == ' ');
  76.       if (s[pos] == 'o' && s[pos + 1] == 'r') pos += 3;
  77.       return neg ? num + n - 1 : num - 1;
  78.     };
  79.     assert(s[pos++] == '(');
  80.     int res = 1;
  81.     while (s[pos] != ')') {
  82.       int var = GetVar();
  83.       if (var >= n) res ^= 1, var -= n;
  84.       eq[i].set(n - var - 1);
  85.     }
  86.     eq[i].set(n, res);
  87.   }
  88.   Gauss(n, eq);
  89. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top