An unsatisfying string \(T\) corresponds to either of \(S_1, S_2, \dots, S_N\), so if an unsatisfying exists, then at least one of \(S_1, S_2, \dots, S_N\) is unsatisfying.
Therefore, it is sufficient to check if, for each \(S\) in \(S_1, S_2, \dots, S_N\), !\({}+S\) is contained in \(S_1, S_2, \dots, S_N\).

This can be determined efficiently with HashSet (unordered_set).

Sample Code (C++)

#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>
using namespace std;

int main(){
    int N;
    cin >> N;
    vector<string> S(N);
    for(string& s : S) cin >> s;
    unordered_set<string> h(S.begin(), S.end());
    for(string& s : S) if(h.count('!' + s)){
        cout << s << endl;
        return 0;
    }
    cout << "satisfiable" << endl;
}

Sample Code (Python)

N = int(input())
S = set(input() for i in range(N))
for s in S:
    if "!" + s in S:
        print(s)
        exit()
print("satisfiable")