Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define dbg() cerr <<
- #define name(x) (#x) << ": " << (x) << ' ' <<
- using namespace std;
- void Gauss(int n, vector<bitset<1024>> &eq) {
- int i = 0, j = 0;
- vector<int> row_idx(n, -1);
- while (i < (int)eq.size() && j < n) {
- bool cont = true;
- for (int k = j; k < (int)eq.size(); ++k) {
- if (eq[k][j]) {
- swap(eq[i], eq[k]);
- cont = false;
- }
- }
- if (cont) {
- ++j;
- continue;
- }
- row_idx[j] = i;
- for (int k = 0; k < (int)eq.size(); ++k) {
- if (eq[k][j]) {
- eq[k] ^= eq[i];
- }
- }
- ++i, ++j;
- }
- vector<int> ans(n, -1);
- for (int i = 0; i < n; ++i) {
- if (row_idx[i] != -1) {
- ans[i] = eq[row_idx[i]][n];
- } else {
- ans[i] = 1;
- }
- }
- for (int i = 0; i < (int)eq.size(); ++i) {
- for (int j = 0; j < n; ++j) {
- eq[i][n] = eq[i][j] ^ (ans[j] & eq[i][j]);
- }
- if (eq[i][n]) {
- cout << "impossible\n";
- return;
- }
- }
- for (int i = n - 1; i >= 0; --i) {
- cout << (ans[i] ? 'T' : 'F');
- }
- cout << endl;
- }
- int main() {
- ios::sync_with_stdio(false);
- cin.tie(0), cout.tie(0);
- int m, n; cin >> m >> n; cin.get();
- vector<bitset<1024>> eq(m);
- for (int i = 0; i < m; ++i) {
- string s; getline(cin, s);
- int pos = 0;
- auto GetVar = [&]() {
- bool neg = false;
- if (s[pos] == 'n') {
- assert(s[pos + 1] == 'o' && s[pos + 2] == 't');
- pos += 4;
- neg = true;
- }
- dbg() name(s) name(pos) endl;
- assert(s[pos++] == 'x');
- int num = 0;
- while (isdigit(s[pos])) {
- num = (num << 1) + (num << 3) + s[pos++] - '0';
- }
- while (s[pos++] == ' ');
- if (s[pos] == 'o' && s[pos + 1] == 'r') pos += 3;
- return neg ? num + n - 1 : num - 1;
- };
- assert(s[pos++] == '(');
- int res = 1;
- while (s[pos] != ')') {
- int var = GetVar();
- if (var >= n) res ^= 1, var -= n;
- eq[i].set(n - var - 1);
- }
- eq[i].set(n, res);
- }
- Gauss(n, eq);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement