[AtCoder] ABC 187 C – 1-SAT

2021年2月3日

問題

方針

英小文字からなる文字列を \( t \) として、\( S_i = t \wedge S_j = !t\) を満たすような \( i, j \) が存在するとき \( t \) は不満な文字列となります。したがって、\( ! \) を含む文字列とそうでない文字列に分けて全探索します。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    int N;
    cin >> N;
    set<string> s1, s2;
    string s;
    for (int i = 0; i < N; i++) {
        cin >> s;
        if (s[0] == '!') {
            s2.insert(s.substr(1));
        } else {
            s1.insert(s);
        }
    }
    for (string t : s1) {
        if (s2.count(t)) {
            cout << t << "\n";
            return 0;
        }
    }
    cout << "satisfiable\n";
    return 0;
}