Submission #2827641

---

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);

const ll M = 1e9 + 9, x = 131;

ll MOD(ll a) {
    if (a >= 0) return a >= M ? a % M : a;
    if (a <= -M) a %= M;
    return a ? a + M : a;
}

ll pwx[N];

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

    pwx[0] = 1;
    for (int i = 1; i < N; ++i)
        pwx[i] = MOD(pwx[i - 1] * x);

    cin >> n >> m;
    fori (i, n)
        cin >> mat[i];

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

            sort(ALL(b));
            do {
                map<int, int> used;
                fori (i, m) {
                    ll cur = 0;
                    ll rev = 0;
                    int j = 0;
                    for (auto &&s : a) {
                        int c = s[i] - 'a' + 1;
                        cur = MOD(cur + c * pwx[j]);
                        rev = MOD(rev + c * pwx[n - 1 - j++]);
                    }

                    for (auto &&s : b) {
                        int c = s[i] - 'a' + 1;
                        cur = MOD(cur + c * pwx[j]);
                        rev = MOD(rev + c * pwx[n - 1 - j++]);
                    }
                    if (used.count(rev)) used.erase(rev);
                    else used[cur] = rev;
                }
                if (SZ(used) > 1) continue;
                if (SZ(used) == 0) answer(1);
                if ((*used.begin()).first == (*used.begin()).second) 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