Post's Teorem

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;

bool inF0(string s) {
    return s[0] == '0';
}

bool inF1(string s) {
    return s.back() == '1';
}

string ten_to_2(int val, int need_size) {
    string s;
    while(val > 0) {
        s.push_back((val % 2) + '0');
        val /= 2;
    }
    for(int i = (int)s.size(); i < need_size; i++) {
        s.push_back('0');
    }
    reverse(s.begin(), s.end());
    return s;
}

bool dominanted(string first, string second) {
    for(int i = 0; i < min(first.size(), second.size()); i++) {
        if(first[i] > second[i]) {
            return false;
        }
    }
    return true;
}

bool inFm(string s) {
    for(int i = 0; i < s.size(); i++) {
        for(int j = 0; j < s.size(); j++) {
            if(i == j) continue;
            string f1 = ten_to_2(i, s.size());
            string f2 = ten_to_2(j, s.size());
            if(dominanted(f1, f2)) {
                if(s[i] > s[j]) {
                    return false;
                }
            }
        }
    }
    return true;
}

bool inFs(string s) {
    for(int i = 0, j = s.size() - 1; i < j; i++, j--) {
        if(s[i] == s[j]) {
            return false;
        }
    }
    return true;
}

string not_string(string& s) {
    string to_return;
    for(char i : s) {
        if(i == '0') to_return.push_back('1');
        if(i == '1') to_return.push_back('0');
    }
    return to_return;
}

bool check_left_right(string&s, int l, int r) {
    if(r - l == 1) {
        return true;
    }
    string f1 = s.substr(0, s.size() / 2);
    string f2 = s.substr(s.size() / 2, s.size() / 2);
    if(f1 == f2 || f1 == not_string(f2)) {
        return check_left_right(f1, l, r/2);
    } else {
        return false;
    }
}

bool inFl(string s) {
    return check_left_right(s, 0, s.size());
}

int main() {
    int n; cin >> n;
    vector<string>functions(n);
    for(int i = 0; i < n; i++) {
        int sz; cin >> sz;
        cin >> functions[i];
    }
    vector<bool>notPost(5, false);
    for(int i = 0; i < n; i++) {
        if(!inF0(functions[i])) {
            notPost[0] = true;
        }
        if(!inF1(functions[i])) {
            notPost[1] = true;
        }
        if(!inFm(functions[i])) {
            notPost[2] = true;
        }
        if(!inFs(functions[i])) {
            notPost[3] = true;
        }
        if(!inFl(functions[i])) {
            notPost[4] = true;
        }
    }
    for(int i = 0; i < 5; i++) {
        if(!notPost[i]) {
            cout << "NO\n";
            return 0;
        }
    }
    cout << "YES\n";
}