Submission #2827619

---

Source Code Expand

#include <iostream>
#include <iomanip>
#include <string>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <vector>
#include <cassert>
#include <fstream>
#include <algorithm>
#include <list>
#include <random>
#include <ctime>
#include <cmath>
#include <random>
#include <bitset>
#include <complex>

using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
//#define int ll
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector< vi > vvi;
typedef vector< vvi > vvvi;
typedef vector<short> vs;
typedef vector<vs> vvs;
typedef vector<vvs> vvvs;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vvl> vvvl;
typedef pair<ld, ld> pld;
typedef complex<double> base;

#define mmin(a, b) a = min(a, (b))
#define mmax(a, b) a = max(a, (b))
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define ALL(a) a.begin(),a.end()
#define sqr(x) (x) * (x)
#define fori(i, n) for(int i = 0; i < int(n); ++i)
#define cint const int &
#define SZ(a) ((int)(a.size()))
#define watch(x) cout << (#x) << " = " << x << endl;

const double PI = 2 * acos(0.0);

template<class T>
void show(const vector<T> &a) {
    for (T x : a)
        cout << x << " ";
    cout << endl;
}

int n, m;
const int N = 12;

string mat[N + 1];

int pop_cnt(int mask);

void answer(bool ok);

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    fori (i, n)
        cin >> mat[i];
    if (!(n & 1)) {
        for (int mask = 0; mask < (1 << n); ++mask) if (pop_cnt(mask) == (n >> 1)) {
                vector<vector<string>> kek(2);
                fori (i, n) {
                    kek[(mask >> i) & 1].pb(mat[i]);
                }
                vector<string> a = kek[0];
                vector<string> b = kek[1];

                sort(ALL(b));
                do {
                    set<string> used;
                    fori (i, m) {
                        string cur = "";
                        for (auto s : a)
                            cur += s[i];
                        for (auto s : b)
                            cur += s[i];
                        string rev = cur;
                        reverse(ALL(rev));
                        if (used.count(rev)) used.erase(rev);
                        else used.insert(cur);
                    }
                    if (SZ(used) == 0) answer(1);
                    else if (SZ(used) > 1) continue;
                    string kek = *used.begin();
                    string lol = kek;
                    reverse(ALL(lol));
                    if (lol == kek) answer(1);
                } while (next_permutation(ALL(b)));
            }
    }
    answer(0);
}

void answer(bool ok) {
    cout << (ok ? "YES" : "NO");
    exit(0);
}

int pop_cnt(int mask) {
    int ret = 0;
    fori (i, n) ret += !((mask >> i) & 1);
    return ret;
}

Submission Info

Judge Result